Zagha doesn't want to remain a weak kid, so he started going to the gym. He has $n$ workouts to do and $m$ muscles to train, each workout trains at most $2$ different muscles of his body, he has to do every workout exactly once, but he doesn't have to train all the muscles.
He needs you to order the workouts such that for every muscle in his body, all the workouts training for this muscle happens consecutively, for example, if Zagha has to do $3$ workouts and has $3$ muscles, where:
Then he can for example do the second workout, then the third, then the first. But he can't do for example first workout, then second then third, because then muscle number $2$ will have two workouts that are not consecutive.
The first line contains $2$ integers $n, m$($ 1 \le n, m \le 5 \cdot 10^5$), the number of workouts, and the number of muscles.
Each of the next $n$ lines describes a workout, each line will start with a $1$ or a $2$, which is the number of muscles this workout trains, followed by the numbers of those muscles, ($ 1 \le$ muscle's number $\le m$), if there are $2$ muscles, their numbers will be different.
If there is no way to order the workouts such that the above condition is satisfied, print "-1" on a single line.
Otherwise print a permutation of size $n$ on a single line, indicating the order Zagha should do the workouts. If there are multiple ways to order the workouts, print any.
In the first example, you can also print "1 3 2".
In the second example, workouts numbers $1$ and $3$ have to be consecutive and workouts numbers $2$ and $4$ have to be consecutive. Also, note that not all muscles have to be trained.
| Input | Output |
|---|---|
3 3 2 2 3 1 1 2 2 1 Copy
|
2 3 1 Copy
|
4 10 1 4 1 9 1 4 1 9 Copy
|
1 3 2 4 Copy
|
3 3 2 1 2 2 2 3 2 3 1 Copy
|
-1 Copy
|
Let the muscles be nodes and the workout be edges, and if the workout trains only a single muscle then it's a self edge(an edge from the node to itself), and let's assume for now that there's no multiple edges.
If there are cycles in the graph then there's no answer(like the third example). So the graph is actually a forest(multiple trees).
Let's divide the nodes into 2 groups, leafs and normal nodes(if a node is adjacent to itself and another node, then it's a normal node), note that if we select an edge(workout) adjacent to a normal node(muscle), then we have to select all of this node's edges right after it.
Now let's look at normal nodes and handle them differently depending on the number of other normal nodes adjacent to them:
And so, if we look at only normal nodes, we can see that they form chains, so the solution becomes to start each chain from one end and remove edges as mentioned above until we reach the other end. Multiple edges doesn't affect this solution. Also don't forget to check leafs that are not adjacent to normal nodes.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
const int N = 1000000;
map<pair<int, int>, vector<int> > mp;
vector<int> g[N + 1];
int n, m, fr[N + 1];
bool vis[N + 1];
vector<int> an;
bool is_main_node(int v){
return g[v].size() >= 2 && v;
}
void no(){
printf("-1\n");
exit(0);
}
pair<int, int> make_p(int a, int b){
if (a > b)swap(a, b);
return make_pair(a, b);
}
void fill_edge(int a, int b){
for (int t: mp[make_p(a, b)])an.push_back(t);
}
void go(int v){
vis[v] = true;
for (int u: g[v])if (!is_main_node(u)){
fill_edge(v, u);
vis[u] = true;
}
for (int u: g[v])if (is_main_node(u) && !vis[u]){
fill_edge(v, u);
return go(u);
}
}
int main() {
scanf("%d%d", &n, &m);
f(i, 1, n + 1){
int s, a, b = 0;
scanf("%d%d", &s, &a);
if (s == 2)scanf("%d", &b);
mp[make_p(a, b)].push_back(i);
g[a].push_back(b);
g[b].push_back(a);
}
f(i, 1, m + 1){
sort(g[i].begin(), g[i].end());
g[i].resize(unique(g[i].begin(), g[i].end()) - g[i].begin());
}
f(i, 1, m + 1)for (int u: g[i])if (is_main_node(u))++fr[i];
f(i, 1, m + 1)if (fr[i]> 2)no();
f(i, 1, m + 1)if (!vis[i] && is_main_node(i) && fr[i] <= 1)go(i);
f(i, 1, m + 1)if (!vis[i] && fr[i] == 0)go(i);
f(i, 1, m + 1)if (!vis[i])no();
f(i, 0, n)printf("%d%c", an[i], i + 1 < n ? ' ' : '\n');
}