ZOJ 3489 Old Labels

Several thousand years ago, there was an ancient kingdom consisting of n cities numbered from 0 to n - 1. The city numbered 0 was the capital of the kingdom and there were n

In the National Library, there was a dusty book in a deep recess which recorded an amazing story. The story said that long long ago, for every road there had been a specified non-negative integer labeled onto it. What's more, for every city, we could find that all the roads starting from it had different labels. So with these labels, every city i could be expressed by the path with a series of numbers pi

One day the king in the kingdom, Takamina, decided to relabel the roads so that the conditions in the story were satisfied. Also, a specified condition should also be met that the list of pi for cities without any road starting from it, namely {pathi}, was lexicographically minimized. To compare two lists, we first sort both lists separately and compare them as strings of paths (do as how strings compare while the elements of the strings are paths). To compare two paths, we also compare them as strings of numbers.

So you, the most talented programmer, can you solve the problem?

Input

There are multiple test cases. The first line of the input is an integer T

For each test case, the first line are two integers n and Q (1 ≤ n ≤ 1000, 0 ≤ Q ≤ n). Next n - 1 lines each containing two integers u and v indicating a road from u to v. Next Q lines each containing one integer c (1 ≤ c ≤ n) indicating a query to the c-th smallest path in {pathi}.

Output

For each query, if there are less than c cities without any road starting from it, print "Out of range." (without quotes), otherwise, print the c-th      

Sample Input

1
8 5
0 1
0 2
0 3
1 4
2 5
3 6
3 7
1
2
3
4
5      

Sample Output

0 0
0 1
1 0
2 0
Out of range.
  Hint      

Labeling the roads to {1, 2, 0, 0, 0, 0, 1} in the order as the sample would lead to the minimized list of paths, which is {{0, 0}, {0, 1}, {1, 0}, {2, 0}}.      

#include<map>
#include<cmath>    
#include<queue> 
#include<string>
#include<vector>
#include<cstdio>    
#include<cstring>  
#include<iostream>
#include<algorithm>    
using namespace std;
#define ms(x,y) memset(x,y,sizeof(x))    
#define rep(i,j,k) for(int i=j;i<=k;i++)    
#define per(i,j,k) for(int i=j;i>=k;i--)    
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])    
#define inone(x) scanf("%d",&x)    
#define intwo(x,y) scanf("%d%d",&x,&y)    
#define inthr(x,y,z) scanf("%lf%lf%lf",&x,&y,&z)    
typedef long long LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 1e3 + 10;
int T, n, m, x, y, a[N], r[N], dep[N], D, to[N][N], v[N][N];
vector<int> f[N], g[N];
pair<int, int> t[N];

void dfs(int x, int d)
{
  dep[x] = d; D = max(d, D);
  for (int i = 0; i < f[x].size(); i++) dfs(f[x][i], d + 1);
}

bool cmp(int x, int y)
{
  for (int i = 0; i < min(g[x].size(), g[y].size()); i++)
  {
    if (r[g[x][i]] < r[g[y][i]]) return true;
    if (r[g[x][i]] > r[g[y][i]]) return false;
  }
  return g[x].size() > g[y].size();
}

bool comp(int x, int y)
{
  return t[x] < t[y];
}

int main()
{
  for (inone(T); T--;)
  {
    intwo(n, m);
    rep(i, 0, n) f[i].clear(), g[i].clear();
    rep(i, 1, n - 1) intwo(x, y), f[x].push_back(y);
    dfs(0, D = 1);
    int cnt = 0;
    per(d, D, 1)
    {
      rep(i, 0, n - 1) if (dep[i] == d)
      {
        if (!f[i].size())
        {
          a[cnt++] = i;
          t[i] = make_pair(-1, -1);
          g[i].push_back(i);
        }
        sort(f[i].begin(), f[i].end(), cmp);
        for (int j = 0; j < f[i].size(); j++)
        {
          v[i][f[i][j]] = j;
          for (int k = 0,u; k < g[f[i][j]].size(); k++)
          {
            u = g[f[i][j]][k];
            g[i].push_back(u);
            t[u] = make_pair(j, r[u]);
            to[i][u] = f[i][j];
          }
        }
      }
      sort(a, a + cnt, comp);
      for (int i = 0, j, k = 0; i < cnt; i = j, k++)
      {
        for (j = i; j < cnt && t[a[i]] == t[a[j]]; j++) r[a[j]] = k;
      }
    }
    while (m--)
    {
      inone(x);
      if (x > cnt) { puts("Out of range."); continue; }
      for (int rt = 0,nt; rt != a[x - 1]; rt = nt)
      {
        if (rt) putchar(' ');
        nt = to[rt][a[x - 1]];
        printf("%d", v[rt][nt]);
      }
      putchar(10);
    }
    putchar(10);
    }
  return 0;
}