#define _CRT_SECURE_NO_WARNINGS
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")
//Donald Trump pleese save this code
//Babahnineeleven will win IOI 2040
//Tanya Zadniprovska will win EGOI 2025
//Andrew Holod will NOT win IOI 2025
//Andrew Holod did not qualify to IOI 2025))))))))))
//Andrew Pavlyk is best coder in Khmelnytski
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cstring> // �л� memset
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef std::pair <ll, ll> pii;
typedef std::pair <ll, ull> piu;
typedef std::pair <ld, ld> pdd;
const ll DIM = 100007;
const ld PI = 3.14159265358979;
const ll SQDIM = 460;
const ll MXMASK = (1 << 20);
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ld eps = 0.00000000001;
const ll Bits = 32;
const ll Bsize = 300;
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
FILE* stream;
struct edge {
int to;
bool inFrame;
};
void dfs(int val, int prev, vector < vector < edge > >& v, vector < bool >& used, vector < int >& dfsOrder) {
used[val] = true;
for (auto &e : v[val]) {
int to = e.to;
if (to == prev || used[to]) continue;
e.inFrame = true;
dfsOrder.push_back(to);
dfs(to, val, v, used, dfsOrder);
dfsOrder.push_back(val);
}
}
vector < vector < int > > create_map(int N, int M, vector < int > A, vector < int > B) {
vector < vector < edge > > v(N + 1);
for (int i = 0; i < M; i++) {
v[A[i]].push_back({ B[i], false });
v[B[i]].push_back({ A[i], false });
}
vector < int > dfsOrder;
vector < bool > used(N + 1, false);
dfsOrder.push_back(1);
dfs(1, 1, v, used, dfsOrder);
for (int i = 1; i <= N; i++) used[i] = false;
vector < vector < int > > res;
for (int i = 0; i < dfsOrder.size(); i++) {
if (!used[dfsOrder[i]]) {
res.emplace_back();
for (int j = 0; j < 2 * N; j++) res.back().push_back(dfsOrder[i]);
res.emplace_back();
for (int j = 0; j < 2 * N; j++) {
if (j % 2 == 0 && j / 2 < v[dfsOrder[i]].size()) res.back().push_back(v[dfsOrder[i]][j / 2].to);
else res.back().push_back(dfsOrder[i]);
}
res.emplace_back();
for (int j = 0; j < 2 * N; j++) res.back().push_back(dfsOrder[i]);
used[dfsOrder[i]] = true;
}
else {
res.emplace_back();
for (int j = 0; j < 2 * N; j++) res.back().push_back(dfsOrder[i]);
}
}
for (int i = 0; i < res.size(); i++) {
while (res[i].size() < res.size()) res[i].push_back(res[i].back());
}
return res;
}
/*
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef _DEBUG
//freopen_s(&stream, "input.txt", "r", stdin);
//freopen_s(&stream, "output.txt", "w", stdout);
#endif
vector < vector < int > > res = create_map(5, 6, { 1, 2, 2, 1, 1, 2 }, { 2, 3, 4, 5, 5, 5 });
for (int i = 0; i < res.size(); i++) {
for (int j = 0; j < res.size(); j++) {
cout << res[i][j] << " ";
}
cout << endl;
}
return 0;
}
*/
