Kolobok: facts and fictions
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
Everyone knows the fairy tale about Kolobok — how a piece of bread broke out of the house, started running along the roads, and met various animals.
Scientists know for a fact what the forest looked like through which Kolobok moved. It consisted of \(n\) clearings, some of which were connected by two-way roads. It is precisely known that there were \(n-1\) roads, and also that from every clearing one could reach any other (possibly passing through other clearings). In addition, it is known that Kolobok started his journey at some clearing, and then walked along a certain number of roads, without visiting any clearing more than once.
However, no one knows for sure what exact route Kolobok took. Many versions have appeared among the people, some of them are quite plausible, and some — complete nonsense. Each version is a certain set of clearings which, as certain people claim, Kolobok definitely visited on his path.
Your task is to determine for each version whether this set could be a set of clearings (possibly incomplete) visited by Kolobok.
Input
The first line contains two integers \(n\) and \(m\) — the number of clearings in the forest and the number of versions, respectively. The clearings are numbered with integers from 1 to \(n\) inclusive.
The next \(n-1\) lines describe the roads, one road per line. Each road is described by a pair of numbers \(a_i\) and \(b_i\) — the numbers of the clearings connected by the corresponding road.
The next \(m\) lines describe the versions, one version per line. The description of a version starts with an integer \(k_i\) — the number of clearings contained in the corresponding version. This is followed by \(k_i\) integers \(p_{ij}\), which specify the numbers of the clearings in the corresponding version (in arbitrary order).
Output
For each version, output Tak if the version is
plausible, and Ni otherwise.
Constraints
40% of tests: \(1 \le n, m, s \le 250\),
60% of tests: \(1 \le n, m, s \le 10^5\),
where \(s\) is the total number of clearings in all versions,
it is guaranteed that in each version all clearing numbers are distinct.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 7 4 4 7 1 4 3 1 3 6 5 3 2 1 1 4 3 1 6 5 3 4 7 2 4 1 2 3 4 | Tak Ni Tak Ni |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|