Problem: ethantree (2018 round1)

Ethan is doing his second programming assignment: implementing pre-order tree
traversal.

Ethan has a binary tree with **N** nodes (numbered 1 to **N**), rooted at node
1. Each node _i_'s left child is node **Ai** (with **Ai** = 0 indicating no
left child), and similarly its right child is **Bi** (with **Bi** = 0
indicating no right child). Each node _i_ is also assigned an integral label
**Li**.

Given such a tree, Ethan must compute its [pre-order
traversal](https://en.wikipedia.org/wiki/Tree_traversal#Pre-order_\(NLR\))
(expressed as a sequence of node labels). The pre-order traversal of a tree
involves taking its root node, then concatenating the pre-order traversal of
the root's left sub-tree (if any), and then concatenating the pre-order
traversal of the root's right sub-tree (if any).

Ethan has attempted to solve this problem, but unfortunately he got his
computer science terms mixed up, and now his algorithm finds the tree's [post-
order traversal](https://en.wikipedia.org/wiki/Tree_traversal#Post-
order_\(LRN\)) instead! The post-order traversal of a tree involves taking the
post-order traversal of the root's left sub-tree (if any), and then
concatenating the post-order traversal of the root's right sub-tree (if any),
and finally concatenating the root node at the end.

Since you were mean to Ethan on his first assignment, you'd like to cheer him
up by making his algorithm work out after all. Though the tree's shape must
stay as is, you can choose a set of labels **L1..N** for its nodes such that
Ethan's algorithm will still produce the correct answer — in other words, such
that the sequence of node labels in the tree's pre-order traversal is equal to
the sequence of node labels in its post-order traversal. Your only two
restrictions are that each node label must be between 1 and **K** (inclusive),
and that every integer between 1 and **K** (inclusive) must be used as the
label of at least one node. You'd like to find any way of validly labelling
the nodes, or determine that no way exists.

### Input

Input begins with an integer **T**, the number of trees. For each tree, there
is first a line containing the space-separated integers **N** and **K**. Then,
**N** lines follow. The _i_th of these lines contains the space-separated
integers **Ai** and **Bi**.

### Output

For the _i_th tree, print a line containing "Case #_i_: " followed by your
chosen node labels **L1..N** separated by spaces, or "Impossible" if there's
no valid way to label the nodes.

### Constraints

1 ≤ **T** ≤ 80  
1 ≤ **K** ≤ **N** ≤ 2,000  
0 ≤ **Ai**, **Bi** ≤ **N**  

Every tree is guaranteed to be a valid binary tree rooted at node 1.

### Explanation of Sample

In the first case, if **L** = [1, 1], then both the pre-order and post-order
label sequences will be [1, 1].

In the second case, for each label between 1 and **K** to be present, you must
choose either **L** = [1, 2] or **L** = [2, 1], both of which would result in
the pre-order and post-order label sequences differing. For example, if **L**
= [1, 2], then the pre-order sequence will be [1, 2] while the post-order
sequence will be [2, 1].

In the third case, if **L** = [2, 2, 1], then the pre-order and post-order
label sequences will both be [2, 1, 2].

Note that other outputs for example cases 3 to 5 would also be accepted.



Sample input:
6
2 1
0 2
0 0
2 2
0 2
0 0
3 2
0 3
0 0
2 0
9 4
2 3
4 0
0 5
6 0
0 7
8 0
0 9
0 0
0 0
15 4
8 0
0 0
0 9
0 0
15 6
0 0
4 0
2 13
0 0
14 12
5 0
3 0
10 11
0 0
0 7
15 3
8 11
0 0
0 9
0 0
15 6
0 0
4 0
2 13
0 0
14 12
5 0
3 0
10 0
0 0
0 7


Sample output:
Case #1: 1 1
Case #2: Impossible
Case #3: 2 2 1
Case #4: 2 4 3 1 3 4 3 2 2
Case #5: 1 1 2 3 4 1 2 3 1 3 1 3 2 3 1
Case #6: Impossible



Code: // Ethan Traverses a Tree
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 2000

int A[LIM],B[LIM];
int cnt[2],ord[2][LIM];

void rec(int z,int i)
{
		if (i<0)
			return;
		if (!z)
			ord[z][cnt[z]++]=i;
	rec(z,A[i]);
	rec(z,B[i]);
		if (z)
			ord[z][cnt[z]++]=i;
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int N,K;
	int i,j,k,a,b;
	vector<int> con[LIM];
	int L[LIM];
	queue<int> Q;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N),Read(K);
				Fox(i,N)
					Read(A[i]),Read(B[i]),A[i]--,B[i]--;
			// compute both traversals
			Fill(cnt,0);
				Fox(i,2)
					rec(i,0);
			// construct graph of nodes with equal labels
				Fox(i,N)
					con[i].clear();
				Fox(i,2)
					Fox(j,N)
						con[ord[i][j]].pb(ord[1-i][j]);
			// split graph into components
			k=0;
			Fill(L,-1);
				Fox(i,N)
					if (L[i]<0)
					{
							if (k<K)
								k++;
						Q.push(i),L[i]=k;
							while (!Q.empty())
							{
								j=Q.front(),Q.pop();
									Fox(a,Sz(con[j]))
										if (L[b=con[j][a]]<0)
											Q.push(b),L[b]=k;
							}
					}
			// output
			printf("Case #%d:",t);
				if (k<K)
					printf(" Impossible\n");
				else
				{
						Fox(i,N)
							printf(" %d",L[i]);
					printf("\n");
				}
		}
	return(0);
}