import sys
sys.setrecursionlimit(300000)
n, m, s = map(int, input().rstrip().split())
graph = [[] for _ in range(n + 1)]
color = [0] * (n + 1)
parent = [0] * (n + 1)
while m > 0:
m -= 1
u, v = map(int, input().rstrip().split())
graph[u].append(v)
def solve():
color[s] = 1
parent[s] = 0
cnt = 2
for i in graph[s]:
assert isinstance(i, int)
color[i] = cnt
parent[i] = s
cnt += 1
def dfs(x):
lst = [x]
while True:
if len(lst) == 0: return None
if len(graph[lst[-1]]) == 0:
lst.pop()
continue
u = graph[lst[-1]].pop()
if color[u] == 0:
color[u] = color[lst[-1]]
parent[u] = lst[-1]
lst.append(u)
elif color[u] == 1 or color[u] == color[lst[-1]]:
pass
else:
return [u, lst[-1]]
for i in graph[s]:
val = dfs(i)
if val and len(val) == 2:
print("Possible")
lst = [val[0]]
while parent[lst[-1]] != 0:
if parent[lst[-1]] < 1 or parent[lst[-1]] > n:
break
lst.append(parent[lst[-1]])
if len(lst) > n: break
print(len(lst))
for i in reversed(lst):
print(i, end=' ')
print()
lst = [val[0], val[1]]
while parent[lst[-1]] != 0:
if parent[lst[-1]] < 1 or parent[lst[-1]] > n:
break
lst.append(parent[lst[-1]])
if len(lst) > n: break
print(len(lst))
for i in reversed(lst):
print(i, end=' ')
print()
return
print("Impossible")
tc = 1
while tc:
solve()
tc -= 1#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <math.h>
#define MAX 200010
#define MM 1000000001
#define ll long long
using namespace std;
int Modul(int x){return x>=0?x: -x;}
vector <int> viz[MAX];
int passou[MAX], w, cam[MAX], end1, end2, t;
bool bfs(int ini){
queue <pair<int,int>> q;
pair<int,int> par;
int no;
for(int i=0;i<viz[ini].size();i++){
q.push(make_pair(viz[ini][i], i+2));
passou[viz[ini][i]]=i+2;
}
passou[ini]=1;
while(!q.empty()){
par=q.front(); q.pop();
//cout << "no=" << par.first << " cor=" << par.second << endl;
no=par.first;
for(int i=0;i<viz[no].size();i++){
if(viz[no][i]!=ini)
if(passou[viz[no][i]]<2){
passou[viz[no][i]]=par.second;
cam[viz[no][i]]=no;
q.push(make_pair(viz[no][i], par.second));
}else if(passou[viz[no][i]]!=par.second){
end1=cam[viz[no][i]]; end2=no; t=viz[no][i];
return true;
}
}
}
return false;
}
int s;
vector <int> caminho(int no){
vector <int> v;
while(cam[no]!=no){
v.push_back(no);
no=cam[no];
}
v.push_back(s);
reverse(v.begin(), v.end());
v.push_back(t);
return v;
}
int main(){
ios_base::sync_with_stdio(0);
int test=1;
//cin >> test;
int n, no, no2, m;
vector <int> c1, c2;
for(int tt=1;tt<=test;tt++){
cin >> n >> m >> s;
for(int i=0;i<=n;i++){
viz[i].clear(); passou[i]=0;
}
cam[s]=s;
for(int i=0;i<m;i++){
cin >> no >> no2;
viz[no].push_back(no2);
}
if(bfs(s)){
cout << "Possible" << endl;
c1=caminho(end1);
c2=caminho(end2);
cout << c1.size() << endl;
for(int i=0;i<c1.size();i++){
cout << c1[i] << " ";
} cout << endl;
cout << c2.size() << endl;
for(int i=0;i<c2.size();i++){
cout << c2[i] << " ";
} cout << endl;
}else{
cout << "Impossible" << endl;
}
}
}
344. Reverse String | 1047. Remove All Adjacent Duplicates In String |
977. Squares of a Sorted Array | 852. Peak Index in a Mountain Array |
461. Hamming Distance | 1748. Sum of Unique Elements |
897. Increasing Order Search Tree | 905. Sort Array By Parity |
1351. Count Negative Numbers in a Sorted Matrix | 617. Merge Two Binary Trees |
1450. Number of Students Doing Homework at a Given Time | 700. Search in a Binary Search Tree |
590. N-ary Tree Postorder Traversal | 589. N-ary Tree Preorder Traversal |
1299. Replace Elements with Greatest Element on Right Side | 1768. Merge Strings Alternately |
561. Array Partition I | 1374. Generate a String With Characters That Have Odd Counts |
1822. Sign of the Product of an Array | 1464. Maximum Product of Two Elements in an Array |
1323. Maximum 69 Number | 832. Flipping an Image |
1295. Find Numbers with Even Number of Digits | 1704. Determine if String Halves Are Alike |
1732. Find the Highest Altitude | 709. To Lower Case |
1688. Count of Matches in Tournament | 1684. Count the Number of Consistent Strings |
1588. Sum of All Odd Length Subarrays | 1662. Check If Two String Arrays are Equivalent |