oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

feedthepenguin Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

feedthepenguin.html

Today, you have been given the honour of preparing a meal for the great Kang the Penguin! You are given N fish, and your job is to create a menu that satisfies the great Penguin's tastes. Being a true gourmet, Kang knows that certain fish might taste delicious when they are eaten immediately after certain others, while others might taste horrible. For example, shark may taste good when served after tuna, or stingray may taste horrible when served after eel. Also, you are guaranteed that for any pair of fishes, at least one tastes nice after the other. Your job now is to create an order with which to feed him some fish such that all of them taste delicious. Note that you can only serve each type of fish once, as Kang appreciates variety. The first fish served will be considered delicious.

Input

The first line of input consists of one integer N. (1 ≤ N ≤ 3,000)

The next N lines of input consist of N integers each, each integer being either 1 or 0.

On the (i+1)-th line, the jth integer represents that fish j tastes nice after fish i if it is 1, or that fish j does not taste nice after fish i if it is 0.

Output

On the first line of output, print a single intege, F, the number of fish which you can serve to him such that all taste delicious.

On the second line of output, print F integers, which represent a possible order to serve the fish in.

Grading

If the first line of output is correct, 20% of the points will be awarded for the test case.

If both lines of the output are correct, 100% of the points will be awarded for the test case.

NOTE: If the first line is wrong and the second is correct, no points will be awarded for the test case.

Sample Input

4
0 1 0 0
0 0 1 0
1 0 0 1
1 1 0 0

Sample Output

4
1 2 3 4

Explanation

There are 4 fishes. After fish 1, only fish 2 can be served. After fish 2, only fish 3 can be served. After fish 3, only fish 1 or 4 can be served. After fish 4, only fish 1 or 2 can be served. Thus, one valid way to serve 4 fishes is 1, followed by 2, followed by 3, followed by 4. An alternative would be 4 1 2 3.

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100203s32MBAverage
2013s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o feedthepenguin -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.