매일마다 우체부인 태양이는 모든 도로에 있는 우체통에 편지를 가지러 우체국을 나온다. 태양이는 힘의 낭비가 싫어 각 도로를 정확히 한번만 방문하길 원한다.

태양이가 사는 마을은 N개의 정점과 M개의 방향성 간선으로 이루어진 그래프로 생각할 수 있다. 정점들은 1번부터 N번까지 번호가 연속적이게 매겨져 있고, 우체국은 1번 정점에 위치해있다.

태양이는 자신의 우체부 생활을 즐기기 위해 각 마을을 돌아보는 순서를 T가지 정했다. 태양이는 자신의 우체부 생활을 확실히 즐기기 위해 이동경로를 계획해야한다.

이동 경로는 다음을 모두 만족해야 한다.

• 각 도로는 정확히 한번만 방문해야 한다. 같은 정점을 여러 번 방문하는 것은 상관없다.
• T개의 순열이 적어도 한번은 각각의 원소가 연속되게 이동경로에 나타나야 한다.
• 태양이의 이동경로는 1번 정점에서 출발하여, 1번 정점으로 끝나야 한다.

입력 형식

• 첫 줄에 마을의 정점의 수와 간선의 수 N, M이 주어진다. (2 ≤ N ≤ 50,000, 1 ≤ M ≤ 200,000)
• 그리고 다음 M줄 동안 간선의 정보 a, b가 주어진다. 이는 a번 마을에서 b번 마을을 향한 방향성 간선이 존재한다는 의미이다. 순서쌍 (a, b)는 입력에 한 번 넘게 주어지지 않는다. (1 ≤ a, b ≤ N, a ≠ b)
• 다음 줄에 만족해야 되는 순열의 개수 T가 주어진다. (0 ≤ T ≤ 10,000)
• 다음 T개의 줄에 각 순열의 정보가 주어진다. 첫 번째에 각 순열의 길이를 나타내는 정수 Ki가 주어진다. (2 ≤ Ki ≤ 200,000) 그리고 정점의 번호를 나타내는 Ki개의 정수가 주어진다. Ki 값들의 합은 1,000,000을 넘지 않는다.

출력 형식

• 첫 줄에 태양이를 만족시키는 경로가 있으면 ‘YES’를, 없으면 ‘NO’를 출력한다.
• 다음에 태양이를 만족시키는 경로를 아무거나 줄로 구분하여 출력한다.

입출력 예

입력
 
6 10
1 5
1 3
4 1
6 4
3 6
3 4
4 3
5 6
6 2
2 1
4
3 1 5 6
3 3 4 3
4 4 3 6 4
3 5 6 2
 
출력 
 
YES
1
3
4
3
6
4
1
5
6
2
1

설명

출처:koi4u 2011 모의고사