#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
// grader
//void InitG(int N, int M){
// cout << N << ' ' << M << endl;
//}
//
//void MakeG(int pos, int u, int v){
// cout << u << ' ' << v << endl;
//}
// end
void Alice(int N, int M, int *A, int *B){
vector <bool> used(N, 0);
vector <pair <int, int>> edge;
edge.emplace_back(N - 1, N);
for (int i = 0; i < M; ++ i){
if (A[i] > B[i]) swap(A[i], B[i]);
edge.emplace_back(A[i], B[i]);
if (A[i] + 1 == B[i]) used[A[i]] = 1;
}
for (int i = 0; i < N - 1; ++ i) if (!used[i]) {
edge.emplace_back(i, i + 1);
edge.emplace_back(i, N);
}
int m = edge.size();
InitG(N + 1, m);
for (int i = 0; i < m; ++ i)
MakeG(i, edge[i].first, edge[i].second);
}
//int main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
//
// int n, m; cin >> n >> m;
// vector <int> u(m), v(m);
// for (int i = 0; i < m; ++ i)
// cin >> u[i] >> v[i];
//
// Alice(n, m, u, v);
//}
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
// grader
//void InitMap(int N, int M){
// cout << N << ' ' << M << endl;
//}
//
//void MakeMap(int u, int v){
// cout << u << ' ' << v << endl;
//}
// end
void Bob(int N, int M, int *C, int *D){
vector <int> deg(N, 0);
vector <vector <int>> adj(N);
for (int i = 0; i < M; ++ i) {
deg[D[i]] ++;
adj[C[i]].push_back(D[i]);
}
queue <int> qu;
for (int i = 0; i < N; ++ i)
if (!deg[i]) qu.push(i);
vector <int> ord(N);
int tot = 0;
while (qu.size()){
int u = qu.front();
qu.pop();
ord[u] = tot ++;
for (int v : adj[u])
if (!--deg[v]) qu.push(v);
}
vector <pair <int, int>> edge;
vector <bool> used(N, 0);
for (int i = 0; i < M; ++ i){
if (ord[D[i]] == N - 1) used[ord[C[i]]] = 1;
else if (ord[C[i]] + 1 < ord[D[i]])
edge.emplace_back(ord[C[i]], ord[D[i]]);
}
for (int i = 0; i < N - 1; ++ i)
if (!used[i]) edge.emplace_back(i, i + 1);
int m = edge.size();
InitMap(N - 1, m);
for (auto [A, B] : edge) MakeMap(A, B);
}
//int main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// srand(time(NULL));
//
// int n, m; cin >> n >> m;
// vector <int> u(m), v(m);
// for (int i = 0; i < m; ++ i) cin >> u[i] >> v[i];
//
// vector <int> pv(n), pe(m);
// iota(pv.begin(), pv.end(), 0);
// iota(pe.begin(), pe.end(), 0);
// random_shuffle(pv.begin(), pv.end());
// random_shuffle(pe.begin(), pe.end());
//
// vector <int> c(m), d(m);
// for (int i = 0; i < m; ++ i) {
// int id = pe[i];
// c[i] = pv[u[id]];
// d[i] = pv[v[id]];
// }
//
// Bob(n, m, c, d);
//}
