Problem C
Uprooted

King Sombra was finally defeated, but at what cost?

The Tree of Harmony, a magical tree that once held the Elements of Harmony—six supernatural artifacts containing the most powerful magic in all of Equestria—was destroyed in the war. Without it, Equestria is the most vulnerable it has ever been.

Though the Tree of Harmony may be physically gone, its spirit lives on in a group of tight-knit friends.

Figure 1: Illustration by Kyle Coate.

Six friends—Gallus, Ocellus, Sandbar, Silverstream, Smolder and Yona—were called to commemorate the Tree of Harmony. To keep its memory alive, they will work together to build a model of what was Equestria’s most powerful protector.

They unfortunately do not recall exactly how the Tree of Harmony looked like, but they have put their heart and soul into its remembrance. After much deep thought, they have reached a consensus on, and are sure of, the following:

1. It was possible to model the Tree of Harmony as $N$ junctions, labeled from $1$ to $N$, connected by branches, such that it was possible to trace a path from any junction to any other junction by using the branches and cutting any single branch made this no longer true.

2. The Tree of Harmony was rooted on the ground at the junction labeled $1$.

3. The Tree of Harmony satisfied $S$ known growth sequences.

   • The $i^\text {th}$ of these growth sequences is a permutation $P_ i$ of the numbers from $2$ to $N$.

   • Consider the $i^\text {th}$ growth sequence $P_ i$, and consider the following process:

     1. Maintain a set $s$ of junctions, originally containing just the root.

     2. Process the elements of $P_ i$ in the order $P_{i, 1}, P_{i, 2}, \dots , P_{i, N-1}$.

     3. When processing the element $P_{i, j}$, there must be at least one branch connecting the junction labeled $P_{i, j}$ and some junction in $s$. Add the junction labeled $P_{i, j}$ to $s$.

     Satisfying $P_ i$ means that the condition in the final step is always true—at least one required branch always exists.

They have not reached an agreement of which branches were actually on the Tree of Harmony, but they have a list of $M$ candidates. The $i^\text {th}$ of these candidate branches connects junctions $A_ i$ and $B_ i$ and has a level of confidence $C_ i$. This value represents the group’s level of confidence that this branch really existed on the Tree of Harmony, such that a larger level of confidence represents more confidence in this branch’s existence.

Figure 2: Illustration of Sample Input 1.

Now, they wish to construct a model of the Tree of Harmony, consistent with the information they have, by selecting a subset of the candidate branches such that the sum total of the levels of confidence of the selected branches is maximized.

Help them accomplish this!

Input

The first line of input contains three integers, $N$ ($2 \leq N \leq 200\, 000$), $M$ ($1 \leq M \leq 200\, 000$) and $S$ ($1 \leq S \leq 200\, 000$; $(N-1)\cdot S \leq 200\, 000$), the number of junctions, the number of candidate branches and the number of growth sequences, respectively.

The next $M$ lines of input contain the descriptions of the candidate branches. In particular, the $i^\text {th}$ of these lines contains three integers $A_ i$, $B_ i$ ($1 \leq A_ i, B_ i \leq N$; $A_ i \neq B_ i$; $A_ i \neq A_ j$ or $B_ i \neq B_ j$ for $i \neq j$; $A_ i \neq B_ j$ or $A_ j \neq B_ i$ for $i \neq j$) and $C_ i$ ($1 \leq C_ i \leq 10^9$), denoting that the $i^\text {th}$ candidate branch connects junctions $A_ i$ and $B_ i$ and has a level of confidence $C_ i$.

The next $S$ lines of input contain the descriptions of the growth sequences. In particular, the $i^\text {th}$ of these lines contains $N-1$ integers $P_{i, 1}, P_{i, 2}, \dots , P_{i, N-1}$ ($2 \leq P_{i, j} \leq N$; $P_{i, j} \neq P_{i, k}$ for $j \neq k$), describing the $i^\text {th}$ growth sequence.

It is guaranteed that $P_ i \neq P_ j$ for $i \neq j$.

Output

If there is no way to select a subset of the candidate branches to form a model of the Tree of Harmony consistent with the information they have, output a single line containing the string IMPOSSIBLE.

Otherwise, on the first line, output a single integer $m$, the number of branches they should select.

On the second line, output $m$ integers $b_1, b_2, \dots , b_ m$ ($1 \leq b_ i \leq M$), denoting the branches that should be selected. All $b_ i$ should be distinct and selecting these branches should result in a model of the Tree of Harmony that is consistent with the information they have, and, among all such consistent models, has the maximum possible sum total of levels of confidence. You can output the branches in any order.

If there are multiple correct answers, you can output any of them.

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

8
1 2 3 5 6 9 10 11

3 1 1
1 2 10
2 3

IMPOSSIBLE

5 6 1
1 2 5
1 3 6
2 3 7
2 4 8
3 4 9
4 5 10
2 3 5 4

IMPOSSIBLE