Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- //#include <ext/pb_ds/assoc_container.hpp>
- //#include <ext/pb_ds/tree_policy.hpp>
- //#include <ext/pb_ds/detail/standard_policies.hpp>
- using namespace std;
- //using namespace __gnu_pbds;
- #define F first
- #define S second
- #define pb push_back
- //#define mt make_tuple
- //#define mp make_pair
- typedef long long ll;
- //typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
- const int rx[4] = {-1, 1, 0, 0};
- const int ry[4] = {0, 0, 1, -1};
- const int N = 100100;
- unordered_map<int, int> mp;
- vector<pair<int, int>> e;
- vector<int> g[N];
- int p[N];
- int n;
- vector<pair<int, int>> ans;
- void dfs(int v, int pr = -1){
- while (p[v] < g[v].size()){
- int i = p[v];
- if (mp.count(g[v][i]) == 1){
- p[v]++;
- continue;
- }
- mp[g[v][i]] = 1;
- int to = (e[g[v][i]].F == v ? e[g[v][i]].S : e[g[v][i]].F);
- p[v]++;
- dfs(to, v);
- }
- if (pr != -1){
- ans.pb({pr, v});
- }
- }
- #define FILE "euler"
- int main() {
- ios_base::sync_with_stdio(0);
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- #else
- freopen(FILE".in", "r", stdin);
- freopen(FILE".out", "w", stdout);
- #endif // LOCAL
- mp.reserve(300000);
- mp.max_load_factor(0.25);
- scanf("%d", &n);
- for (int i = 0; i < n; i++){
- int k;
- scanf("%d", &k);
- while (k--){
- int x;
- scanf("%d", &x);
- if (x - 1 < i) continue;
- e.pb({i, x - 1});
- g[i].pb(e.size() - 1);
- g[x - 1].pb(e.size() - 1);
- }
- p[i] = 0;
- }
- vector<int> _ch;
- for (int i = 0; i < n; i++){
- if (g[i].size() % 2 == 1){
- _ch.pb(i);
- }
- }
- if (_ch.size() != 0 && _ch.size() != 2){
- printf("-1\n");
- return 0;
- }
- bool rev = false;
- int start = 0;
- if (_ch.size() == 2){
- rev = true;
- int a = _ch[_ch.size() - 1];
- int b = _ch[_ch.size() - 2];
- start = a;
- vector<bool> bad(g[a].size(), false);
- int p = 0;
- for (int x : g[a]){
- if (e[x].F == b || e[x].S == b){
- bad[p] = true;
- }
- p++;
- }
- vector<int> cur = g[a];
- g[a].clear();
- for (int i = 0; i < cur.size(); i++){
- if (!bad[i]){
- g[a].pb(cur[i]);
- }
- }
- for (int i = 0; i < cur.size(); i++){
- if (bad[i]){
- g[a].pb(cur[i]);
- }
- }
- // e.pb({a, b});
- // g[a].pb(e.size() - 1);
- // swap(g[a][0], g[a].back());
- // g[b].pb(e.size() - 1);
- // swap(g[b][0], g[b].back());
- }
- dfs(start);
- reverse(ans.begin(), ans.end());
- // if (rev) {
- // ans.pop_back();
- // }
- printf("%d\n", ans.size());
- for (auto to : ans) printf("%d ", to.F + 1);
- printf("%d ", ans.back().S + 1);
- //#ifdef LOCAL
- // cerr << "TIME = " << fixed << 1.0 * clock() / CLOCKS_PER_SEC << endl;
- //#endif // LOCAL
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement