시간 제한메모리 제한제출정답맞은 사람정답 비율
3 초 1024 MB94333046.875%

문제

제제가 아끼는 라임 오렌지 나무인 밍기뉴는 정점의 개수가 $N$, 간선의 개수가 $N-1$인 연결 그래프이다. 밍기뉴의 $i$번 간선에는 $a_i$개의 라임 오렌지가 달려 있다. 제제와 포르투가는 밍기뉴 위에서 게임을 하려고 한다. 첫 번째 턴에는 제제가 밍기뉴의 뿌리인 $r$에 말을 놓고, 각 턴마다 두 사람은 다음 과정을 반복한다.

  • 말이 놓인 정점과 인접한 간선을 아무거나 선택한다.
  • 선택한 간선에 있는 라임 오렌지를 1개 이상 딴다.
  • 말을 선택한 간선의 반대편 정점으로 이동한다.

더 이상 턴을 진행할 수 없을 때, 즉 말이 놓인 정점과 인접한 어느 간선에도 딸 라임 오렌지가 없을 때 그 턴의 플레이어는 게임에서 패배한다. $r = 1, 2, \cdots, N$일 때, 제제가 이긴다면 "Zeze", 포르투가가 이긴다면 "Portuga"를 따옴표 없이 출력하는 프로그램을 작성하자.

입력

첫 번째 줄에는 밍기뉴의 정점의 개수 $N$이 주어진다.

두 번째 줄부터 $N$번째 줄까지 $N-1$개의 줄에 간선과 그 간선에 달린 라임 오렌지의 개수가 $x_i \ y_i \ a_i$의 형태로 주어진다.

출력

$r = 1, 2, \cdots, N$일 때 제제가 이긴다면 "Zeze", 포르투가가 이긴다면 "Portuga"를 따옴표 없이 각각 $N$ 개의 줄에 걸쳐 출력한다.

제한

  • $1 \le N \le 3 \times 10^5$
  • $1 \le a_i \le 10^9$

서브태스크

번호 배점 제한
1 7

밍기뉴의 정점 중 차수가 2 이상인 정점은 최대 1개 존재한다.

2 18

밍기뉴의 각 정점의 최대 차수는 2이다.

3 33

$n \leq 3000$

4 42

추가적인 제약 조건이 없다.

예제 입력 1

3
3 1 1
1 2 1

예제 출력 1

Zeze
Portuga
Portuga

예제 입력 2

20
19 2 837009437
19 3 555623333
9 6 932422073
7 11 384958865
5 7 279037157
19 5 301909012
9 14 577327858
10 15 372601829
10 16 965167094
13 10 840904695
1 13 927245827
4 1 133242826
12 4 276397978
19 12 736742142
8 17 642702689
9 8 70136361
9 18 971340052
19 9 307149033
19 20 523797433

예제 출력 2

Zeze
Portuga
Portuga
Zeze
Portuga
Portuga
Zeze
Zeze
Zeze
Zeze
Portuga
Zeze
Zeze
Portuga
Portuga
Portuga
Zeze
Portuga
Zeze
Portuga

출처

Contest > Orange Cup > Orange Cup B번

채점 및 기타 정보

  • 예제는 채점하지 않는다.