25316번 - 수소철도 충전 시스템 스페셜 저지

문제

탄소중립 시대를 맞아 한국에도 수소철도가 도입되었다. 정부는 UCPC차량사업소를 수소열차를 위한 거점 기지로 지정하여 여기에 수소철도 관련 업무를 모두 맡기려고 한다.

선우는 수소철도 연료 충전 시스템을 담당하여 충전소를 관리하는 임무를 맡았다. 현재 UCPC차량사업소에서 충전소로 사용하는 시설에는 $N$개의 교차로가 있고 $N-1$개의 레일이 교차로 사이를 트리 형태로 연결하고 있다. 교차로의 번호는 1ドル$ 이상 $N$ 이하의 서로 다른 정수이다. 모든 레일의 길이는 열차 1ドル$량의 길이와 같기 때문에, 충전소에 열차가 주차한다면 특정 두 교차로를 연결하는 단순 경로 위에 열차를 세워 열차의 각 칸(1ドル$량)이 레일 하나를 차지하도록 할 수 있다.

모든 레일은 단선으로 설치했기 때문에 한 레일 위에는 최대 한 대의 열차만 주차할 수 있다. 다만, 열차의 칸과 칸 사이를 이어 주는 통로는 고무 재질로 잘 휘기 때문에 교차로에서는 여러 열차가 겹칠 수 있다.

일부 교차로에는 충전기가 설치되어 있다. 열차를 충전하려면 열차의 기관실이 있는 한쪽 끝이 충전기가 있는 교차로에 닿도록 주차해서 충전기와 기관실을 연결해야 한다. 열차마다 제조사나 규격이 모두 다르기 때문에 각 열차는 특정 교차로에 있는 충전기만 사용할 수 있다.

철도 운행 상황에 따라 충전소에 들어오는 열차의 상황이 시시각각 달라지기 때문에 선우는 열차 배치 시스템을 개발하려고 한다. 충전소에 열차가 총 $T$대가 들어오는데, $j$(1ドル\leq j\leq T$)번째 열차는 길이가 $l_j$량이고 반드시 $p_j$번 교차로에 있는 충전기를 사용해야 한다.

그림 C.1: 첫 번째 예제에서 열차를 배치하는 예시

선우는 여러 열차가 같은 레일을 쓰지 않도록 열차를 배치하는 게 생각보다 어렵다는 것을 파악하고 당신에게 도움을 요청하였다. 충전소와 열차의 정보가 주어지면 적절하게 열차를 배치하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 교차로의 수 $N$이 주어진다. $(2\leq N\leq 500,円 000)$

이후 $N-1$줄에 걸쳐 레일들의 정보가 주어진다. 이 중 $i$번째 줄에는 두 개의 정수 $s_i$와 $e_i$가 공백으로 구분되어 주어지며, 이는 $i$번째 레일이 $s_i$번 교차로와 $e_i$번 교차로를 연결함을 의미한다. $(1\leq s_i,e_i\leq N)$

주어지는 레일들은 교차로들을 트리 형태로 연결하고 있음이 보장된다.

$N+1$번째 줄에는 충전해야 할 열차의 수 $T$가 주어진다. $(1\leq T<N)$

이후 $T$줄에 걸쳐 열차들의 정보가 주어진다. 이 중 $j$번째 줄에는 두 개의 정수 $p_j$와 $l_j$가 공백으로 구분되어 주어지며, 이는 $j$번째 열차의 충전기가 $p_j$번 교차로에 있고, 열차의 길이는 $l_j$량임을 의미한다. $(1\leq p_j\leq N$; 1ドル\leq l_j<N)$

출력

만약 열차 $T$대를 모두 충전하는 방법이 없다면 첫 번째 줄에 NO를 출력한다.

만약 열차 $T$대를 모두 충전할 수 있다면 첫 번째 줄에 YES를 출력하고, 두 번째 줄부터 $T$개의 줄에 걸쳐 열차의 배치를 출력한다. 이 중 $j$번째 줄에는 두 개의 정수 $p_j$와 $q_j$를 출력해야 하며, 이는 $j$번째 열차를 $p_j$번 교차로와 $q_j$번 교차로를 연결하는 단순 경로 위에 배치함을 의미한다. 이때 이 단순 경로의 길이는 $l_j$여야 하며, 여기서 출력하는 $p_j$는 입력으로 주어진 $j$번째 열차의 충전기의 위치 $p_j$와 동일해야 한다. $(1\leq p_j,q_j\leq N)$

가능한 답이 여러 가지라면 그중 아무거나 출력한다.

제한

힌트