Lucy는 Xeppelin 대회의 삽화를 준비하고 있습니다. 한 문제를 위해 그녀는 그래프를 그려달라는 요청을 받았습니다. 문제는 멋진 그래프를 그리기가 쉽지 않다는 점입니다.
Lucy는 $n$개의 정점과 $m$개의 간선을 가진 무방향 연결 그래프를 그리기에 가장 좋은 곳이 모눈종이라고 생각합니다. 그래프의 각 정점은 격자의 정수 점 $(x, y)$가 되고, 각 간선은 어떤 정수 $x$와 $y$에 대해 점 $(x, y) \leftrightarrow (x + 1, y)$ 또는 $(x, y) \leftrightarrow (x, y + 1)$을 잇는 선분이 됩니다. 모눈 패턴의 일부를 강조 표시하기만 하면 삽화가 완성됩니다!
하지만 그림이 그래프에서의 거리를 보존한다면 더욱 좋을 것입니다. 공식적으로, 2차원 평면에서 정수 좌표를 가지는 점들을 생각해 봅시다. 그림(drawing)이란 이러한 $n$개의 점으로 이루어진 배열 $p_1, \dots, p_n$입니다. 가능한 모든 $i$와 $j$에 대해 $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$를 만족하면 그 그림을 멋지다(nice)고 합니다. 여기서 $\operatorname{dist}(u, v)$는 그래프에서 정점 $u$와 $v$ 사이의 최단 경로에 있는 간선의 개수로 정의되며, $\operatorname{Manhattan}(p_i, p_j)$는 평면 위의 두 정수 점 $p_i$와 $p_j$ 사이의 맨해튼 거리로 정의됩니다.
주어진 그래프에 대해 멋진 그림을 찾거나, 존재하지 않음을 판별하십시오.
입력
각 테스트는 여러 개의 테스트 케이스를 포함합니다. 첫 번째 줄에는 테스트 케이스의 개수 $t$ ($1 \le t \le 50\,000$)가 주어집니다. 이어서 테스트 케이스의 설명이 주어집니다.
각 테스트 케이스의 첫 번째 줄에는 그래프의 정점 수와 간선 수를 나타내는 두 정수 $n$과 $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$)이 주어집니다.
다음 $m$개의 줄에는 각각 그래프의 간선으로 연결된 두 정점을 나타내는 두 정수 $u$와 $v$ ($1 \le u, v \le n$, $u \ne v$)가 주어집니다. 그래프는 연결되어 있습니다.
모든 테스트 케이스에서 $n$의 합과 $m$의 합은 모두 $500\,000$을 초과하지 않습니다.
시각적 편의를 위해 모든 테스트 케이스 앞에 빈 줄이 하나씩 있습니다. 이는 무시해도 됩니다.
출력
각 테스트 케이스마다 멋진 그림이 존재하지 않으면 한 줄에 "NO"를 출력합니다.
그렇지 않으면 첫 번째 줄에 "YES"를 출력합니다. 그 후 멋진 그림의 예시를 출력합니다. 이어지는 $n$개의 줄에는 각각 $i$번째 점의 좌표를 나타내는 두 정수 $x_i$와 $y_i$ ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$)를 출력해야 합니다. 가능한 답이 여러 개라면 그중 아무것이나 하나를 출력합니다.
예제
예제 입력 1
3 4 4 1 2 2 3 3 4 4 1 5 4 1 2 1 3 1 4 1 5 7 8 1 2 1 3 2 4 3 4 4 5 4 6 5 7 6 7
예제 출력 1
YES 0 0 1 0 1 1 0 1 YES 3 1 2 1 3 0 4 1 3 2 YES 1 2 2 2 1 3 2 3 3 3 2 4 3 4
예제 입력 2
2 6 6 1 2 2 3 3 4 4 5 5 6 6 1 12 16 1 2 1 3 2 4 3 4 3 5 4 6 5 6 6 7 4 8 7 8 7 9 8 10 9 10 8 11 10 12 11 12
예제 출력 2
NO NO