/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 2e5 + 10;
int n, m, t[maxn][2], sz[maxn];
set < int > pos[maxn];
vector < int > g[2 * maxn];
vector < pair < int, int > > ans;
int used[maxn];
vector < int > path;
void dfs(int v)
{
used[v] = 1;
path.push_back(v);
for (int u : g[v])
{
if (used[u])
continue;
dfs(u);
}
}
void solve_chain(vector < int > ch)
{
if (ch[1] <= m)
reverse(ch.begin(), ch.end());
for (int i = 1; i < ch.size(); i += 2)
{
int p1 = ch[i - 1], p2 = ch[i], j = 0;
if (p2 > m)
{
p2 -= m;
j = 1;
}
t[p1][1] = t[p2][j];
t[p2][j] = 0;
ans.push_back({p2, p1});
sz[p2] --;
sz[p1] ++;
}
}
void move_at(int i, int j)
{
t[j][sz[j]] = t[i][sz[i] - 1];
t[i][sz[i] - 1] = 0;
sz[i] --;
sz[j] ++;
ans.push_back({i, j});
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= m; i ++)
{
cin >> t[i][0] >> t[i][1];
}
for (int i = 1; i <= m; i ++)
{
if (t[i][0] == t[i][1] && t[i][0] != 0)
continue;
if (t[i][0] != 0)
sz[i] ++;
if (t[i][1] != 0)
sz[i] ++;
for (int j = 0; j < sz[i]; j ++)
{
pos[t[i][j]].insert(j * m + i);
}
if (sz[i] == 2)
{
g[i].push_back(m + i);
g[m + i].push_back(i);
}
}
for (int i = 1; i <= n; i ++)
{
int l = *pos[i].begin();
pos[i].erase(l);
int r = *pos[i].begin();
pos[i].erase(r);
g[l].push_back(r);
g[r].push_back(l);
}
queue < vector < int > > chn, cyc;
for (int i = 1; i <= 2 * m; i ++)
{
if (!used[i] && g[i].size() == 1)
{
path.clear();
dfs(i);
chn.push(path);
}
}
for (int i = 1; i <= 2 * m; i ++)
{
if (!used[i] && g[i].size() > 0)
{
path.clear();
dfs(i);
cyc.push(path);
}
}
while(true)
{
if (!chn.empty())
{
path = chn.front();
/// cout << path.size() << endl;
chn.pop();
int up = -1;
for (int i = 1; i < path.size(); i ++)
{
if (path[i] > m && path[i - 1] > m)
{
up = i - 1;
break;
}
}
if (up == -1)
{
solve_chain(path);
}
else
{
int cur = 1;
while(cur <= m && t[cur][0] != 0)
cur ++;
if (cur > m)
{
cout << -1 << endl;
exit(0);
}
t[cur][0] = t[cur][1] = t[path[up] - m][1];
t[path[up] - m][1] = 0;
t[path[up + 1] - m][1] = 0;
sz[path[up] - m] --;
sz[path[up + 1] - m] --;
sz[cur] = 2;
ans.push_back({path[up] - m, cur});
ans.push_back({path[up + 1] - m, cur});
vector < int > left, right;
for (int i = 0; i < up; i ++)
left.push_back(path[i]);
for (int i = up + 2; i < path.size(); i ++)
right.push_back(path[i]);
chn.push(left);
chn.push(right);
}
}
else
if (!cyc.empty())
{
path = cyc.front();
cyc.pop();
vector < int > db;
for (int i = 1; i < path.size(); i ++)
{
if (path[i] > m && path[i - 1] > m)
{
db.push_back(i - 1);
break;
}
}
if (db.size() == 0)
{
int idx = 0;
while(true)
{
int row1 = path[idx];
int row2 = path[idx + 1];
if (row1 > m)
row1 -= m;
if (row2 > m)
row2 -= m;
if (row1 == row2)
idx ++;
else
{
break;
}
}
int cur = 1;
while(cur <= m && t[cur][0] != 0)
cur ++;
if (cur > m)
{
cout << -1 << endl;
exit(0);
}
vector < int > new_chain;
if (path[idx] > m)
{
//cout << path[idx] << " : " << path[idx + 1] << endl;
move_at(path[idx] - m, cur);
new_chain.push_back(cur);
for (int i = idx + 1; i < path.size(); i ++)
new_chain.push_back(path[i]);
for (int i = 0; i < idx; i ++)
new_chain.push_back(path[i]);
/** for (int i = 0; i < new_chain.size(); i ++)
cout << new_chain[i] << " ";
cout << endl;*/
}
else
{
move_at(path[idx + 1] - m, cur);
new_chain.push_back(cur);
for (int i = idx; i >= 0; i --)
new_chain.push_back(path[i]);
for (int i = (int)(path.size()) - 1; i > idx + 1; i --)
new_chain.push_back(path[i]);
}
chn.push(new_chain);
}
else
if (db.size() > 0)
{
int cur = 1;
while(cur <= m && t[cur][0] != 0)
cur ++;
if (cur > m)
{
cout << -1 << endl;
exit(0);
}
int up = path[db[0]];
t[cur][0] = t[cur][1] = t[path[up] - m][1];
t[path[up] - m][1] = 0;
t[path[up + 1] - m][1] = 0;
sz[path[up] - m] --;
sz[path[up + 1] - m] --;
sz[cur] = 2;
ans.push_back({path[up] - m, cur});
ans.push_back({path[up + 1] - m, cur});
vector < int > new_chain;
for (int i = up - 1; i >= 0; i --)
new_chain.push_back(path[i]);
for (int i = (int)(path.size()) - 1; i > up + 1; i --)
new_chain.push_back(path[i]);
chn.push(new_chain);
}
/**else
{
int
}*/
///cout << "Here" << endl;
}
else
{
break;
}
}
cout << ans.size() << endl;
for (pair < int, int > cur : ans)
{
cout << cur.first << " " << cur.second << endl;
}
}
int main()
{
solve();
return 0;
}
/**
3 5
1 2
3 2
1 3
0 0
*/
Compilation message
Main.cpp: In function 'void solve_chain(std::vector<int>)':
Main.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = 1; i < ch.size(); i += 2)
| ~~^~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:140:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for (int i = 1; i < path.size(); i ++)
| ~~^~~~~~~~~~~~~
Main.cpp:175:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
175 | for (int i = up + 2; i < path.size(); i ++)
| ~~^~~~~~~~~~~~~
Main.cpp:187:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
187 | for (int i = 1; i < path.size(); i ++)
| ~~^~~~~~~~~~~~~
Main.cpp:229:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
229 | for (int i = idx + 1; i < path.size(); i ++)
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19028 KB |
Output is correct |
| 2 |
Partially correct |
12 ms |
19000 KB |
Output is partially correct |
| 3 |
Correct |
10 ms |
19040 KB |
Output is correct |
| 4 |
Correct |
10 ms |
19052 KB |
Output is correct |
| 5 |
Correct |
10 ms |
19104 KB |
Output is correct |
| 6 |
Correct |
10 ms |
19028 KB |
Output is correct |
| 7 |
Correct |
10 ms |
19004 KB |
Output is correct |
| 8 |
Correct |
10 ms |
19028 KB |
Output is correct |
| 9 |
Correct |
9 ms |
19068 KB |
Output is correct |
| 10 |
Correct |
9 ms |
19028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
183 ms |
63584 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
38664 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
38664 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19028 KB |
Output is correct |
| 2 |
Partially correct |
12 ms |
19000 KB |
Output is partially correct |
| 3 |
Correct |
10 ms |
19040 KB |
Output is correct |
| 4 |
Correct |
10 ms |
19052 KB |
Output is correct |
| 5 |
Correct |
10 ms |
19104 KB |
Output is correct |
| 6 |
Correct |
10 ms |
19028 KB |
Output is correct |
| 7 |
Correct |
10 ms |
19004 KB |
Output is correct |
| 8 |
Correct |
10 ms |
19028 KB |
Output is correct |
| 9 |
Correct |
9 ms |
19068 KB |
Output is correct |
| 10 |
Correct |
9 ms |
19028 KB |
Output is correct |
| 11 |
Runtime error |
183 ms |
63584 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
