// Testneveles Ora.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <unordered_set>
using namespace std;
int main()
{
int pCount, qCount; //People, Query
cin >> pCount >> qCount;
vector<vector<int>> Neighbours(pCount+1); //Points at bigger ppl
vector<int> PeopleSmallerCount(pCount+1); //return smallest->highest
int SplitIndex = -1; // switch SplitIndex and SplitIndex+1
for (size_t i = 0; i < qCount; i++)
{
int s, b;
cin >> s >> b;
Neighbours[s].push_back(b);
PeopleSmallerCount[b]++;
}
queue<int> nextInLine;
vector<int> Inverted;
unordered_set<int> Excluded;
for (size_t i = 1; i <= pCount; i++)
{
if (PeopleSmallerCount[i] == 0) nextInLine.push(i);
}
while (nextInLine.size() != 0) {
Inverted.push_back(nextInLine.front());
if (nextInLine.size() > 1 && SplitIndex == -1) {
SplitIndex = Inverted.size() - 1;
}
for (size_t i = 0; i < Neighbours[nextInLine.front()].size(); i++)
{
if (Excluded.count(Neighbours[nextInLine.front()][i]) == 0) {
PeopleSmallerCount[Neighbours[nextInLine.front()][i]]--;
if (PeopleSmallerCount[Neighbours[nextInLine.front()][i]] == 0) nextInLine.push(Neighbours[nextInLine.front()][i]);
}
}
Excluded.insert(nextInLine.front());
nextInLine.pop();
}
/*cout << Inverted.size();*/
for (size_t i = 1; i <= pCount; i++)
{
if (Excluded.count(i) == 0 && PeopleSmallerCount[i] == 0) {
SplitIndex = Inverted.size() - 1;
Inverted.push_back(i);
}
}
if (SplitIndex == -1 && Inverted.size() == pCount) { // only 1 solution
cout << "1\n";
for (size_t i = 0; i < Inverted.size(); i++)
{
cout << Inverted[i] << " ";
}
return 0;
}
if (Inverted.size() != pCount) { // 0 solutions //Bug is here
cout << "0\n";
return 0;
}
if (Inverted.size() == pCount && SplitIndex!=-1) { // 2 solutions
cout << "2\n";
for (size_t i = 0; i < Inverted.size(); i++)
{
cout << Inverted[i] << " ";
}
cout << "\n";
int a = Inverted[SplitIndex];
Inverted[SplitIndex] = Inverted[SplitIndex + 1];
Inverted[SplitIndex + 1] = a;
for (size_t i = 0; i < Inverted.size(); i++)
{
cout << Inverted[i] << " ";
}
return 0;
}
}
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu
// Tips for Getting Started:
// 1. Use the Solution Explorer window to add/manage files
// 2. Use the Team Explorer window to connect to source control
// 3. Use the Output window to see build output and other messages
// 4. Use the Error List window to view errors
// 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
// 6. In the future, to open this project again, go to File > Open > Project and select the .sln file