Problem: service_trees (2019 quals)

Carlos is hoping to strike it rich with his new consulting firm, Carlos
Structures Industries (CSI). With a solid mission statement and a can-do
attitude, he's sure to succeed in the wide world of bespoke data structures.

_ "Our vision is to synergistically leverage our core competencies to deliver
competitive market solutions that assertively meet our clients' needs." _

His first client, the well-known translation firm Treehouse, is looking to
update their logo. Treehouse wants their logo to be a rooted tree with **N**
nodes numbered 1 through **N**. They have a rough idea of what the tree should
look like, but they want Carlos to finish fleshing it out. In particular, they
have **M** requirements, the _i_th of which states that the [lowest common
ancestor](https://en.wikipedia.org/wiki/Lowest_common_ancestor) of nodes
**Xi** and **Yi** must be node **Zi**.

Carlos's goal is to find any valid tree consistent with all of these
requirements if possible, or to determine that no such tree exists.

### Input

Input begins with an integer **T**, the number of tree designs. For each
design, there is first a line containing the space-separated integers **N**
and **M**. Then **M** lines follow, the _i_th of which contains the space-
separated integers **Xi**, **Yi**, and **Zi**.

### Output

For the _i_th design, print a line containing "Case #_i_: " followed by a
description of a valid rooted tree if possible, or the string "Impossible" if
no valid tree exists. A tree description is **N** space-separated integers,
the _j_th of which is node _j_'s parent (or 0 if node _j_ is the root).

### Constraints

1 ≤ **T** ≤ 100  
2 ≤ **N** ≤ 60  
1 ≤ **M** ≤ 120  
1 ≤ **Xi**, **Yi**, **Zi** ≤ **N**  
**Xi** ≠ **Yi**

### Explanation of Sample

In the first case, the LCA of nodes 1 and 2 in the chosen tree is 3, as
required. This is the only valid output for this case.

In the third case, "2 3 0 3" would also be accepted, while no other outputs
would be.

In the fifth and sixth cases, multiple possible outputs would be accepted.



Sample input:
6
3 1
1 2 3
3 3
1 2 2
2 3 3
3 1 1
4 2
2 1 2
1 4 3
6 3
2 4 3
6 5 4
1 2 6
7 4
7 3 5
4 1 2
6 3 6
6 4 5
12 9
1 5 7
11 2 6
9 4 12
8 12 6
10 1 7
4 3 12
3 10 6
8 11 8
2 5 10


Sample output:
Case #1: 3 3 0
Case #2: Impossible
Case #3: 3 0 2 3
Case #4: Impossible
Case #5: 2 0 6 5 2 5 5
Case #6: 7 10 12 12 10 0 6 6 12 7 8 6



Code: // Trees as a Service
// 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 MAXN 60
#define MAXM 120

int N,M;
int X[MAXM],Y[MAXM],Z[MAXM],P[MAXN];

bool BuildTree(int par,vector<int> nodes)
{
	int s=Sz(nodes);
	int i,j,k,a,b,c;
	bool here[MAXN]={0};
	bool good;
		Fox(i,s)
			here[nodes[i]]=1;
	// consider each possible root
		Fox(i,s)
		{
			// compute nodes which must or must not be in the same subtree
			int r=nodes[i];
			vector<int> con[MAXN];
			set<PR> badp;
			vector<vector<int> > subtrees;
			bool used[MAXN]={0};
				Fox(j,M)
					if (here[a=X[j]] && here[b=Y[j]] && here[c=Z[j]])
						if (a==r || b==r)
						{
							// LCA of pair including root must be equal to root
							if (c!=r)
								goto Bad;
						}
						else
						if (c==r)
						{
							// pair with LCA equal to root must be in different subtrees
							badp.insert(mp(a,b));
							badp.insert(mp(b,a));
						}
						else
						{
							// otherwise, triple must be in the same subtree
							con[a].pb(b);
							con[b].pb(a);
							con[a].pb(c);
							con[c].pb(a);
						}
			// floodfill to compute subtrees
				Fox(j,s)
					if (j!=i && !used[k=nodes[j]])
					{
						vector<int> subtree;
						queue<int> Q;
						Q.push(k),used[k]=1;
							while (!Q.empty())
							{
								k=Q.front(),Q.pop();
								subtree.pb(k);
									Fox(a,Sz(con[k]))
										if (!used[b=con[k][a]])
											Q.push(b),used[b]=1;
							}
							Fox(a,Sz(subtree))
								Fox(b,a)
									if (badp.count(mp(subtree[a],subtree[b])))
										goto Bad;
						subtrees.pb(subtree);
					}
			// recursively attempt to build each subtree
			P[r]=par;
				Fox(j,Sz(subtrees))
					if (!BuildTree(r,subtrees[j]))
						return(0);
			return(1);
Bad:;
		}
	return(0);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int i;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N),Read(M);
				Fox(i,M)
					Read(X[i]),Read(Y[i]),Read(Z[i]),X[i]--,Y[i]--,Z[i]--;
			// recursively build tree, and output
			Fill(P,-1);
			vector<int> nodes;
				Fox(i,N)
					nodes.pb(i);
			printf("Case #%d: ",t);
				if (!BuildTree(-1,nodes))
					printf("Impossible\n");
				else
				{
					Fox(i,N)
						printf("%d%c",P[i]+1,(i==N-1)?'\n':' ');
				}
		}
	return(0);
}