City Map
yo homies👬👦👬 need a 🍹juicy af🍹 city🌆 map fo' yo 💡lit💡 parties🎉.
thine city🌆 got pads🏠, num🅱ering 💯ranging🚜 from to . but yaw broke💲✖😭 so . each pad🏠 go to exactly won of thy homies👬👦👦, represented🙋 by num🅱ers 💯ranging🚜 from to . exactly won1⃣, homie not too2⃣ or free3⃣.. an each pair✌ of y'all 🍆🍆🍆 distincth pads🏠 iz eider 🔁connected🔁 by won 🅱ridge🌉 or no 🅱ridge🌉 at all. ain't no 🅱ridge🌉 🔁connect🔁 a pad🏠 to itself, an yo 🅱ridges🌉 can be ✝crosseth✝ in 🅱oth ➡directions⬅.
yo planning parties🎉, . each party whence'st💦💦💧 a sequence🔤 of ya og homies👬👦👦. to make a party🎉 lit🔥 thoust start🏁 visiting any of da pads🏠 of da first1⃣ homie👦. from each pad🏠, thee ✝crosseth✝️ a 🅱ridge🌉 to visit a pad🏠 of da next⏭️ homie👬, until thine in a pad🏠 of da last🚫️ homie👬. if diz possible👍👌 the party do be called📞 spicy🌶🌶🌶.
thou need👅👅👅 to ✝crosseth✝️ a 🅱ridge🌉; y'all 🚷can't🚷 stay at da same pad🏠. thine allowed👌✅👍 to ✝crosseth✝️ the same 🅱ridge🌉 mo' dan wons, yaw can even ✝crosseth✝️ the same 🅱ridge🌉 twice✌✌✌ in a row. dat sum sick😵😵😵 moves!
can yo make a 🍹juicy af🍹 city🌆 map to make each of yo 💡lit af💡 parties🎉 spicy🌶🌶🌶? if yo game🏀 fo' it, show👀👀 the map🗺️, and show👀👀 a sequence🔤 of pads🏠 makin' each party🎉. if da task impossible😭😭😭, output dude, big l.
Translation
Your friends need a city map for your parties.
Your city has houses, numbered from to , and . Each house is assigned to exactly one of your friends, numbered from to . Each pair of distinct houses is either connected by one bridge, or no bridge at all. No bridge connects a house to itself, and bridges can be crossed in both directions.
You are planning parties, . A party is a sequence of your friends. To celebrate a party, you start by visiting any of the houses assigned to the first friend. From each house, you take a bridge to visit a house assigned to the next friend, until you reach a house assigned to the last friend. If this is possible, the party is called spicy.
You need to cross a bridge: staying at the same house doesn't count. You are allowed to use the same bridge multiple times, and even cross the same bridge twice in a row.
Can you construct a city map such that each party is spicy? If you can, show the map, and show a sequence of houses that form each party. If it is impossible, output dude, big l.
Input Format
The first line of input contains , the number of test cases.
The first line of each test case contains a single integer , the number of parties.
The next lines describe each of the parties. In particular, the th line contains space-separated integers, the first of which is , and the rest is the sequence in order. ( is defined as the length of sequence .)
Constraints
Every element of every sequence is between and , inclusive.
Subtask 1 (30 points):
Subtask 2 (70 points):
Output Format
In the first line of each test case, if constructing a city map is possible, output the number of houses in the city.
In the next line, output integers, where the th integer is the number of the friend who owns the th house.
The next lines should each contain a string of length . The string should consist of only the characters 0 and 1. The th character of the th string should be 0 if houses and are not connected by a bridge, and 1 if they are.
The last lines should contain space-separated integers each, representing the sequence of houses visited in each party.
For a test case, if constructing a city map is not possible, output dude, big l.
Sample Input
2
3
2 10 20
2 20 30
2 30 10
3
4 1 2 4 5
3 1 3 5
4 1 3 4 5
Sample Output
3
10 20 30
011
101
110
1 2
2 3
3 1
6
1 2 1 3 4 5
001100
001010
110000
100011
010101
000110
3 2 5 6
1 4 6
1 4 5 6
Explanation
The first test case asks us to make a map for three parties, each of length .
It is possible to construct a map for all parties using houses. Houses , , and are assigned to friends , , and , respectively.
The first party should start at a house assigned to friend and ends at a house assigned to friend . Indeed, we can start at house and end at house . The other parties can be explained similarly.
The second test case shows that it is possible for a friend to be assigned multiple houses.
xxxxxxxxxxusing namespace std;int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0;}