Commuter trains do not change tracks

A suburban railway has $N$ stations and $M$ segments connecting them. Any two stations are connected by at most one segment. The segment network is arranged so that, starting from any station, you can return to it only by traveling at least one segment twice. Commuter trains run on the railway. Each train travels in both directions along its own route between two terminal stations and stops at every intermediate station.

For the convenience of passengers, the railway management decided to introduce a new fare system. Under this system, each station is assigned an integer called its tariff number. The fare between two stations without transfers is determined by the absolute difference of the tariff numbers of those stations. The tariff numbers of stations along the route of each train must change monotonically, that is, strictly increase when moving in one direction and therefore strictly decrease when moving in the opposite direction. This ensures that the fare grows as the number of segments traveled increases.

Write a program that assigns a tariff number to each station.

	4 stations, 3 segments: 1-4, 2-4, 3-4Routes: 1-4-2, 2-4-3, 3-4-1.Answer: no solution
	5 stations, 4 segments: 1-5, 2-5, 3-5, 4-5Routes: 1-5-2, 2-5-3, 3-5-4, 4-5-1.Answer: a solution exists; for example, the following one:station number: 1 2 3 4 5tariff number: 1 4 1 5 3Note: tariff numbers of different stations may coincide.

The first line of the input file contains two integers: $N$, the number of stations $(2 \le N \le 100\,000)$, and $M$, the number of segments between them $(1 \le M \le N - 1)$. The following $M$ lines contain pairs of integers $a, b$ $(a \ne b, 1 \le a \le N, 1 \le b \le N)$, meaning there is a segment between stations $a$ and $b$. After them, on a separate line, a single positive integer $K$ is given, the number of train routes. The following $K$ lines contain descriptions of train routes, one per line. Each description is a sequence of integers, the numbers of all stations of the route in the order of one of the two possible directions of travel. A route description ends with the number 0.

All station numbers in a route description are distinct. The number of stations in each route is at least two. Any two consecutive stations in the route of each train are connected by a segment. The total number of stations in the descriptions of all routes does not exceed 200,000. There may be stations and segments that no train passes through.

In the first line of the output file, print "NO" if the required assignment of tariff numbers does not exist. Otherwise, in the first line print "YES", and in the next line print $N$ positive integers, where the $i$-th number is the tariff number of the $i$-th station. The tariff number of each station must be in the range from 1 to $N$.

If several solutions exist, print any one of them.