분할 통치

어떤 왕국을 두 명의 왕이 함께 다스린다. 왕국에는 마을이 $N$개 있고, 마을 사이는 방향이 없는 도로로 이어져 있다. 모든 도로는 두 왕 중 정확히 한 명이 소유하며, 두 왕이 같은 도로를 함께 소유하는 일은 없다. 각 왕은 도로를 정확히 $N-1$개 소유하고, 그 도로만 써도 어느 마을에서 어느 마을로든 갈 수 있다. 같은 두 마을을 잇는 도로가 여러 개 있을 수도 있다.

악한 군주가 이 왕국을 정복하려 한다. 왕국을 갈라놓고 치는 편이 쉬우므로, 군주는 도로를 되도록 적게 부수어서 서로 오갈 수 없는 두 마을 $X$와 $Y$가 생기게 만들려고 한다. 부수어야 하는 도로의 최소 개수와, 그만큼만 부수는 방법의 수를 구하라. 부순 도로의 집합이 다르면 다른 방법으로 센다. 방법의 수가 커질 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫째 줄에 마을의 개수 $N$이 주어진다. ($2 \le N \le 10^5$)

다음 $N-1$개 줄에는 정수 $a_i$, $b_i$가 두 개씩 주어진다. 첫 번째 왕이 마을 $a_i$와 마을 $b_i$를 잇는 도로를 소유한다는 뜻이다. ($1 \le a_i, b_i \le N$)

그다음 $N-1$개 줄에도 정수 $a_i$, $b_i$가 두 개씩 주어진다. 두 번째 왕이 마을 $a_i$와 마을 $b_i$를 잇는 도로를 소유한다는 뜻이다. ($1 \le a_i, b_i \le N$)

왕국을 둘로 갈라놓으려면 부수어야 하는 도로의 최소 개수와, 그만큼만 부수는 방법의 수를 $10^9 + 7$로 나눈 나머지를 공백으로 구분해 한 줄에 출력한다.