Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P153PROD - ROUND 3D - Khôi phục hành trình

Sau khi tìm được trạm đích của chuyến di dân, các trạm bắt tay vào xây dựng các không gian liên kết để di chuyển, liên kết giữa các trạm tạo thành một đồ thị dạng cây mà nút gốc chính là trạm đích cần di chuyển đến, người dân ở các trạm di chuyển từ nút lá lên các nút cha của nó dần dần lên nút gốc. Vì lý do an ninh nên hành trình của chuyến đi không được tiết lộ chi tiết mà chỉ tiết lộ trạm gần nhất mà hai trạm bất kì sẽ gặp nhau.

Cooper thấy khá hứng thú với hành trình này nên anh quyết định tìm cho ra bằng được. Các bạn hãy giúp anh ấy.

Input

Dòng đầu tiên chứa số tự nhiên n là số trạm (1 ≤ n ≤ 150).

n dòng sau, dòng thứ i chứa chứa n số nguyên, số thứ j - f[i][j] - chính là trạm gần nhất mà trạm i và trạm j sẽ gặp nhau. Đặc biệt f[i][j] = i nếu trạm j di chuyển trực tiếp đến trạm i và ngược lại, quy ước f[i][i] = i.

Output

Một dòng n số nguyên, số thứ i là nút cha của nút i, nếu nút i không có nút cha thì bằng 0.

Example

Input:
3
1 1 1
1 2 1
1 1 3 Output: 0 1 1

Test 2:
Input:
7
1 1 3 3 3 1 1
1 2 3 3 3 1 1
3 3 3 3 3 3 3
3 3 3 4 4 3 3
3 3 3 4 5 3 3
1 1 3 3 3 6 1
1 1 3 3 3 1 7

Output:
3 1 0 3 4 1 1

Hình vẽ minh họa test 2:


Được gửi lên bởi:adm
Ngày:2015-03-19
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2016-04-13 03:35:33
HD:
http://mycodealgorithm.blogspot.com/2016/04/p153prod-round-3d-khoi-phuc-hanh-trinh.html
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.