ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2016

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Magic Programmer

Time limit: 5.0 second
Memory limit: 256 MB
There are lots of projects in one well-known Ural IT company. In many of them, unfortunately, there are some issues with the development process: deadlines are not met, system fails under load, users are dissatisfied. Luckily, Ivan, a magic programmer, works at the company. He is able to enter a project and raise the level of development to a principally higher level in almost no time, so that everything starts working without a hitch. After that there is no point for him to stay in the project, as everything is fine here, while there are lots of other projects that only Ivan can save. Such employee is very much appreciated in the company, and they always try to redirect him to the most problem-plagued place.
Ivan has some requirements of his own: not only wants he to save projects, but to learn new technologies as well. At the moment he is interested in m technologies not yet studied. Ivan used to play ACM in those old times when the program was allotted 1MB of RAM, and one could do not that much during the available one second of time, so he got used to value time and not to waste it. Ivan has decided that, since he is destined to travel from one project to another, during his time in the company he should, firstly, work with all technologies that are of interest to him, and, secondly, should not employ any same technology in various projects (this is boring and would deprive him of originality-related emotions that are so essential to him in his work). He also cannot, surely, enter one project twice.
There are n projects at the company in total. Due to various reasons, direct transfers between projects are not always possible. There are n−1 pairs of projects allowing direct transfer (either way). Yet one can get from a project to any other via several direct transfers, not entering a single project twice, and there’s only one way to do that. Each project employs some subset of technologies that are interesting to Ivan. Help Ivan choose the first project and to draw up a plan of transfers so that he does not enter a single project twice and tries each of the m technologies exactly one time.


The first line contains two integer numbers n and m (1 ≤ n, m ≤ 105) separated by space.
The following n−1 lines contain descriptions of allowed direct transfers between projects. j-th line contains two different numbers uj and vj (1 ≤ uj, vjn) — numbers of projects allowing direct transfer. It is guaranteed that the specified transfer system meets the aforementioned conditions.
Next n lines describe the technologies Ivan is interested in, that are used in each of the projects. i-th line starts with a number ai (0 ≤ aim), equal to number of technologies of interest to Ivan used in the project i. Then in the same line, separated by space, ai of various integer numbers between 1 and m follow — the numbers of these technologies.
It is guaranteed that the sum of all ai does not exceed 106.


If a plan meeting Ivan’s requirements does not exist, output a single line "No solution" (without quotes).
Otherwise output two numbers s and t — the numbers of the first and the last projects at the suitable transfer plan.
If several solutions exist, output any.


5 3
1 2
1 3
3 4
3 5
1 1
1 3
2 1 3
1 2
2 5
3 3
1 2
1 3
2 2 3
3 1 2 3
1 3
2 2
2 3
1 2
2 1 2
2 1 3
No solution


In the second example there is no sense for Ivan to make any transfers, so he will spend all his career in the project 2, where he will try all technologies. So the numbers of the first and the second project match.
Problem Author: Alexander Fetisov
To submit the solution for this problem go to the Problem set: 2085. Magic Programmer