1167C.cpp

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define vt vector
#define ll long long
#define pb push_back
#define ioa insert_or_assign
#define umap unordered_map
#define prq priority_queue
#define F first
#define S second
#define all(c) (c).begin(), (c).end()
#define rev(c) (c).rbegin(), (c).rend()
#define sz(x) (int)(x).size()
#define mset(ar, val) memset(ar, val, sizeof(ar))
#define en '\n'

const int d4r[4] = {-1,0,1,0}; const int d4c[4] = {0,1,0,-1};
const int d8r[8] = {-1,-1,0,1,1,1,0,-1}; const int d8c[8] = {0,1,1,1,0,-1,-1,-1};
const int INF = 0x3f3f3f3f; const int mINF = 0xc0c0c0c0;
const ll LINF = 0x3f3f3f3f3f3f3f3f; const ll mLINF = 0xc0c0c0c0c0c0c0c0;
int T = 1;

const int mx = 5*1e5;
vt<int> adj[2*mx+1];
int dist[2*mx+1];
int n,m;
vt<int> res(mx+1);

void bfs(int s) {
	queue<int> q;
	q.push(s);
	dist[s] = 1;
	int cnt = 1;
	vt<int> ppl;
	ppl.pb(s);

	while(!q.empty()) {
		int curr = q.front(); q.pop();

		for(int i=0; i<sz(adj[curr]); ++i) {
			int next = adj[curr][i];

			if(dist[next] > 0) continue;  // visited
			if(next > mx) dist[next] = cnt;
			else {
				dist[next] = cnt + 1;
				ppl.pb(next);
			}
			q.push(next);

			cnt = max(cnt, dist[next]);
		}
	}
	for(int x : ppl) {
		res[x] = cnt;
	}
	return;
}

void sol() {
	mset(dist,0);
	cin >> n >> m;
	for(int i=1; i<=m; ++i) {
		int k;
		cin >> k;
		int x;
		for(int j=0; j<k; ++j) {
			cin >> x;
			adj[x].push_back(i+mx);
			adj[i+mx].pb(x);
		}
	}

	for(int i=1; i<=n; ++i) {
		if(dist[i] == 0) {
			bfs(i);
		}
	}
	for(int i=1; i<=n; ++i) {
		cout << res[i] << ' ';
	}
	cout << en;

	return;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	while(T--) {
		sol();
	}

	return 0;
}