//D
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5+10;
const int maxm = 4e5+10;
struct Edge{
	int from,to,next,cnt;
	Edge(int from = 0,int to = 0,int next = 0):from(from),to(to),next(next){}
}edge[maxn];
int head[maxn],cnt,d,dep[maxn],p[maxn];
bool vis[maxn],col[maxn];
void addedge(int f,int t){
	edge[cnt] = Edge(f,t,head[f]);
	head[f] = cnt++;
}
int n,m,k;
void DFS(int u){
	if(vis[u])return;
	vis[u] = 1;
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].to;
		if(vis[v] and dep[v] > dep[u]){
			vector<int>cir = {};
			int cur = v;
			while(cur != u){
				cir.push_back(cur);
				cur = p[cur];
			}
			cir.push_back(u);
			int s = cir.size();
			cout << 2 << endl << s << endl;
			for(int yay:cir)cout << yay << " ";
			exit(0);
		}
		else if(!vis[v]){
			p[v] = u;
			dep[v] = dep[u]+1;
			col[v] = !col[u];
			DFS(v);
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	memset(head,-1,sizeof(head));
	cin >> n >> m >> k;
	d = ceil((double)k/2);
	for(int i = 1;i <= m;i++){
		int f1,t1;
		cin >> f1>> t1;
		if(f1 > k or t1 > k)continue;
		addedge(f1,t1);
		addedge(t1,f1);
	}
	int cnt1 = 0; 
	for(int i = 1;i <= n;i++)DFS(i);
	vector<int>ans = {};
	for(int i = 1;i <= n;i++)if(col[i])cnt1++;
	int qwq = 0;
	if(cnt1 >= d)qwq = 1;
	for(int i = 1;i <= n;i++)if(col[i] == qwq){
		if((int)ans.size() == d)break;
		ans.push_back(i);
	}
	cout << 1 << endl;
	for(int x:ans)cout << x << " ";
	return 0;
}

//UVA11107
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e3+10,maxs = 105;
const ull x = 13331;
int n;
ull xp[maxn],H[maxn][maxs];
string raw[maxs];
vector<string>ans;
bool check(int L){
	bool ok = 0;
	map<ull,int>cnt;
	for(int k = 1;k <= n;k++){
		map<ull,bool>vis;
		for(int i = 1;i+L-1 <= raw[k].size();i++){
			ull u = H[i+L-1][k] - H[i-1][k]*xp[L];
			if(!vis[u]){
				vis[u] = 1;
				cnt[u]++;
				if(cnt[u] >= n/2+1)ok = 1;
			}
		}
	}
	return ok;
}
void solve(int L){
	map<ull,int>cnt;
	for(int k = 1;k <= n;k++){
		map<ull,bool>vis;
		for(int i = 1;i+L-1 <= raw[k].size();i++){
			ull u = H[i+L-1][k] - H[i-1][k]*xp[L];
			if(!vis[u]){
				vis[u] = 1;
				cnt[u]++;
				if(cnt[u] >= n/2+1){
					string yay = "";
					for(int j = i;j <= i+L-1;j++)yay += raw[k][j-1];
					ans.push_back(yay);
				}
			}
		}
	}
	return;
} 
int main(){
	xp[0] = 1;
	for(int i = 1;i < maxn;i++)xp[i] = xp[i-1]*x;
	bool wtf = 0; 
	while(scanf("%d",&n) == 1 and n){
		if(wtf)cout << endl;
		wtf = 1;
		ans.clear();
		for(int i = 1;i <= n;i++){
			string u;
			cin >> u;
			raw[i] = u;
			for(int j = 1;j <= u.size();j++)H[j][i] = H[j-1][i]*x + u[j-1] - 'a';
		}
		int L = 1,R = maxn,M,len = 0;
		while(L <= R){
			M = (L+R)/2;
			if(check(M)){
				len = M;
				L = M+1;
			}
			else R = M-1;
		}
		solve(len);
		sort(ans.begin(),ans.end());
		if(ans.size() and len){
			for(int i = 0;i < ans.size();i++)if(!i or ans[i] != ans[i-1])cout << ans[i] << endl;
		}
		else cout << "?\n";
	}
	return 0;
}

//C 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
typedef long long ll;
int pre[maxn];
int main(){
	ll a,b,c,d,ans = 0;
	cin >> a >> b >> c >> d;
	for(int i = a;i <= b;i++)pre[i+b]++,pre[i+c+1]--;
	for(int i = 1;i < maxn;i++)pre[i] += pre[i-1];
	for(int i = 0;i < maxn;i++)ans += pre[i]*max(0ll,min(d,(ll)(i-1)) - c + 1); 
	cout << ans;
	return 0;
}

//CF1325E
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
const int maxm = 1e7+10;
struct Edge{
	int f,t,next;
	Edge(int f = 0,int t = 0,int next = 0):f(f),t(t),next(next){}
}edge[maxn];
int cnt,head[maxn],dis[maxn],ans = 1e9;
void addedge(int f,int t){
	edge[cnt] = Edge(f,t,head[f]);
	head[f] = cnt++;
}
void add(int f,int t){
	addedge(f,t);
	addedge(t,f);
}
bool visp[maxn],vis[maxn];
vector<int>P,d[maxn];
int n,raw[maxn];
void init(){
	visp[1] = 1;
	for(int i = 2;i < maxn;i++)if(!visp[i]){
		for(int j = i*2;j < maxn;j+=i)visp[j] = 1;
	}
	for(int i = 2;i < maxn;i++)if(!visp[i]){
		P.push_back(i);
	}
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> raw[i];
		int cur = raw[i];
		if(!visp[cur]){
			d[i].push_back(cur);
			continue;
		}
		for(int j = 2;j*j <= raw[i];j++){
			int cnt2 = 0;
			while(cur%j == 0){
				cur /= j;cnt2++;
			}
			if(cnt2%2)d[i].push_back(j);
		}
		if(cur > 1)d[i].push_back(cur);
	}
	for(int i = 1;i <= n;i++){
		if(!d[i].size()){
			cout << 1;
			exit(0);
		}
		else if(d[i].size() == 1){
			add(1,d[i][0]);
		}
		else add(d[i][0],d[i][1]);
	}
}
void BFS(int s){
	memset(dis,-1,sizeof(dis));
	dis[s] = 0;
	queue<pair<int,int> >q;
	q.push(make_pair(s,0));
	while(!q.empty()){
		auto now = q.front();
		q.pop();
		int u = now.first,fa = now.second;
		for(int i = head[u];~i;i = edge[i].next){
			int v = edge[i].t;
			if(v == fa)continue;
			if(dis[v] == -1){
				dis[v] = dis[u]+1;
				q.push(make_pair(v,u));
			}
			else{
				ans = min(ans,dis[v]+dis[u]+1);
			}
		}
	}
}
int main(){
	memset(head,-1,sizeof(head));
	init();
	for(int i = 1;i <= 1010;i++)BFS(i);
	if(ans == 1e9)ans = -1;
	cout << ans;
	return 0;
}

for(int l = 1;l <= n;l = r+1){
		if(k/l)r = min(n,k/(k/l));
		else r = n;
		ans += (r-l+1)*(k/l);
	}

//CF906D 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
ll raw[maxn],n,mod;
map<ll,ll>vis;
ll phi(ll x){
	int m = (ll)sqrt(x+0.5);
	ll tans = x;
	for(int i = 2;i <= m;i++)if(!(x%i)){
		tans = tans/i*(i-1);
		while(!(x%i))x /= i;
	}
	if(x > 1)tans = tans / x * (x-1);
	return tans;
}
inline ll upd(ll x,ll p){
	return x<p?x:x%p+p;
}
ll Pow(ll x,ll d,ll p){
	ll tans = 1;
	if(d == 0)return 1;
	ll a = Pow(x,d/2,p);
	tans = upd(a*a,p);
	if(d%2)tans = upd(tans*x,p); 
	return upd(tans,p);
}
ll cal(ll l,ll r,ll p){
	if(l == r or p == 1)return upd(raw[l],p);
	else return Pow(raw[l],cal(l+1,r,vis[p]),p);
}
int main(){
	cin >> n >> mod;
	ll qwq = mod;
	while(qwq != 1){
		vis[qwq] = phi(qwq);
		qwq = vis[qwq];
	}
	vis[1] = 1;
	for(int i = 1;i <= n;i++)cin >> raw[i];
	int q;
	cin >> q;
	while(q--){
		int l,r;
		cin >> l >> r;
		cout << cal(l,r,mod)%mod << endl;
	}
	return 0;
}

//C
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6+10;
int raw[maxn];
int vis[maxn];
ll Pow(int x,int d){
	ll tans = 1;
	if(d == 0)return 1;
	ll a = Pow(x,d/2);
	tans = a*a;
	if(d%2)tans = tans*x; 
	return tans;
}
bool n_prime[maxn];
vector<int>p[maxn],d[maxn];
void prime(){
	for(int i = 2;i <maxn;i++){
		if(!n_prime[i]){
			p[i].push_back(i); 
			for(int j = i*2;j < maxn;j += i){
				n_prime[j] = 1;
				p[j].push_back(i);
			}
		}
	}
	n_prime[1] = 1;
}
int main(){
	prime();
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++)cin >> raw[i];
	for(int i = 1;i <= n;i++){
		int u = raw[i];
		for(int x:p[u]){
			int yay = 0;
			while(u%x == 0){
				yay++;
				u /= x;
			}
			d[x].push_back(yay);
		}
	}
	ll ans = 1;
	for(int i = 2;i < maxn;i++){
		sort(d[i].begin(),d[i].end());
		if(d[i].size() == n-1){
			ans *= Pow(i,d[i][0]);
		}
		else if(d[i].size() > n-1)ans *= Pow(i,d[i][1]); 
	}
	cout << ans;
	return 0;
}

typedef long long ll;
typedef long double ld;
const double PI = 3.14159265358979; 
const int maxn = 1e5+10;
struct Point{
	ld x,y;
	Point(ld x = 0,ld y = 0):x(x),y(y){}
	Point operator + (Point B){return Point(x+B.x,y+B.y);}
	Point operator - (Point B){return Point(x-B.x,y-B.y);}
	Point operator * (ld w){return Point(x*w,y*w);}
	Point operator / (ld w){return Point(x/w,y/w);}
	Point Rotate_90_clock(){return Point(y,-x);}//顺时针旋转90°
	ld len2(){return x*x + y*y;}//长度的平方
	ld len(){return(sqrt(x*x + y*y));}
    bool operator < (const Point & A) const{
		return (x == A.x?y < A.y:x < A.x);
	}
}point[maxn];
struct Circle{
	Point O;
	ld R;
	Circle(Point O = Point(0,0),ld R = 0):O(O),R(R){}
	ld R2(){return R*R;}
};
typedef Point Vector;
ld Dot(Vector A,Vector B){
	return A.x*B.x + A.y*B.y;
}//点积
ld Cross(Vector A,Vector B){
	return A.x*B.y - A.y*B.x;
}//二维叉积
Point Line_inter(Point P0,Point V0,Point P1,Point V1){
	ld t = Cross(P1 - P0,V1)/Cross(V0,V1);
	return P0 + V0 * t;
}//返回两向量交点.P和V分别为向量起点终点*
Circle p2circle(Point A,Point B){
	Circle tans = Circle((A+B)/2,0);
	tans.R = (tans.O - A).len();
	return tans;
}//两点的外接圆
Circle p2circle(Point A,Point B,Point C){
	Circle tans = Circle(Line_inter((A+B)/2,(B - A).Rotate_90_clock(),(A+C)/2,(C - A).Rotate_90_clock()),0);
	tans.R = (tans.O - A).len();
	return tans;
}//三点共圆
typedef Point Vector;
inline double to_rad(double deg){
	return deg*(PI/180);
}
Vector Rotate(Vector A,double rad){//逆时针 
	return Vector(A.x*cos(rad) - A.y*sin(rad),A.x*sin(rad) + A.y*cos(rad));
}

ld LinePointDist(Point p,Point a,Point b){//点到直线
	Vector v1 = b-a,v2 = p-a;
	return fabs(Cross(v1,v2) / len(v1));
}
ld SegPointDist(Point p,Point a,Point b){//点到线段
	if(a == b)return len(p - a);
	Vector v1 = b-a,v2 = p-a,v3 = p-b;
	if(Dot(v1,v2) < eps)return len(v2);
	if(Dot(v1,v3) > eps)return len(v3);
	return LinePointDist(p,a,b);
}

void rotate(ld & x,ld & y,ld theta,ld rx,ld ry){
    ld nx = (x - rx)*cos(theta) - (y - ry)*sin(theta) + rx;
    ld ny = (x - rx)*sin(theta) + (y - ry)*cos(theta) + ry;
    x = nx,y = ny;
}

vector<Point> ConvexHull(vector<Point>raw){
    if(raw.size() == 1)return raw;
	sort(raw.begin(),raw.end());
	int n = raw.size(),idx = 0;
	vector<Point>hull(2*n+10);
	for(int i = 0;i < n;i++){
		while(idx > 1 and Cross(hull[idx-1] - hull[idx-2],raw[i] - hull[idx-1]) <= 0)idx--;
		hull[idx++] = raw[i];
	}
	int k = idx;
	for(int i = n-2;i >= 0;i--){
		while(idx > k and Cross(hull[idx-1] - hull[idx-2],raw[i] - hull[idx-1]) <= 0)idx--;
		hull[idx++] = raw[i];
	}
	hull.resize(idx-1);
	return hull;
}

vector<Point> minkowski(vector<Point> & C1,vector<Point> & C2){
	int n = (int)C1.size(),m = (int)C2.size();
	vector<Point>s1(n),s2(m),A(n+m+10);
	for(int i = 0;i < n-1;i++)s1[i] = C1[i+1] - C1[i];
	s1[n-1] = C1[0] - C1[n-1];
	for(int i = 0;i < m-1;i++)s2[i] = C2[i+1] - C2[i];
	s2[m-1] = C2[0] - C2[m-1];
	int tot = 0;
	A[tot] = C1[0] + C2[0];
	int p1 = 0,p2 = 0;
	while(p1 < n and p2 < m){
		tot++;
		A[tot] = A[tot-1] + (Cross(s1[p1],s2[p2]) >= eps?s1[p1++]:s2[p2++]);
	}
	while(p1 < n){
		++tot;
		A[tot] = A[tot-1] + s1[p1++];
	}
	while(p2 <= m){
		++tot;
		A[tot] = A[tot-1] + s2[p2++];
	}
	A.resize(tot+1);
	return A;
}

double PolyArea(Point * _Point,int n){
	double area = 0;
	for(int i = 2;i < n;i++){
		area += Cross(_Point[i] - _Point[1],_Point[i+1] - _Point[1]);
	}
	return area/2; 
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e5+10;
struct Point{
	ld x,y;
	Point(ld x = 0,ld y = 0):x(x),y(y){}
	Point operator + (Point B){return Point(x+B.x,y+B.y);}
	Point operator - (Point B){return Point(x-B.x,y-B.y);}
	Point operator * (ld w){return Point(x*w,y*w);}
	Point operator / (ld w){return Point(x/w,y/w);}
	Point Rotate_90_clock(){return Point(y,-x);}//顺时针旋转90°
	ld len2(){return x*x + y*y;}//长度的平方
	ld len(){return(sqrt(x*x + y*y));}
}point[maxn];
struct Circle{
	Point O;
	ld R;
	Circle(Point O = Point(0,0),ld R = 0):O(O),R(R){}
	ld R2(){return R*R;}
};
typedef Point Vector;
ld Dot(Vector A,Vector B){
	return A.x*B.x + A.y*B.y;
}//点积
ld Cross(Vector A,Vector B){
	return A.x*B.y - A.y*B.x;
}//二维叉积
Point Line_inter(Point P0,Point V0,Point P1,Point V1){
	ld t = Cross(P1 - P0,V1)/Cross(V0,V1);
	return P0 + V0 * t;
}//返回两向量交点.P和V分别为向量起点终点*
Circle p2circle(Point A,Point B){
	Circle tans = Circle((A+B)/2,0);
	tans.R = (tans.O - A).len();
	return tans;
}//两点的外接圆
Circle p2circle(Point A,Point B,Point C){
	Circle tans = Circle(Line_inter((A+B)/2,(B - A).Rotate_90_clock(),(A+C)/2,(C - A).Rotate_90_clock()),0);
	tans.R = (tans.O - A).len();
	return tans;
}//三点共圆
Circle Min_Cir_Cover(Point * point,int n){
	random_shuffle(point+1,point+n+1);
	Circle res;
	for(int i = 1;i <= n;i++){
		if((point[i] - res.O).len2() > res.R2()){
			res = Circle(point[i],0);
			for(int j = 1;j < i;j++){
				if((point[j] - res.O).len2() > res.R2()){
					res = p2circle(point[i],point[j]);
					for(int k = 1;k < j;k++){
						if((point[k] - res.O).len2() > res.R2()){
							res = p2circle(point[i],point[j],point[k]);
						}
					}
				}
			}
		}
	}
	return res;
}//最小圆覆盖,输入点集数组和点的数量,返回一个圆

bool Left(Point P,Point A,Point B) {
	return Cross(B - A,P - A) > 0;
}
bool Right(Point P,Point A,Point B) {
	return Cross(P - A,B - A) > 0;
}
bool Point_in_Convex(Point P,vector<Point> & C){
	int n = C.size();
	if (Left(P,C[0],C[n - 1]) or Right(P,C[0],C[1]))return 0;
	int l = 1, r = n - 1;
	while (l < r - 1) {
		int m = (l + r) / 2;
		if (Left(P, C[0], C[m])) {
			l = m;
		}
		else {
			r = m;
		}
	}
	if (!Right(P, C[l], C[r]))return 1;
	return 0;
}

const int maxn = 2e5+10;
const int maxm = maxn*2;
int head[maxn],pa[maxn];
bool vis[maxn];
struct Edge{
	int f,t,next;
	Edge(int f = 0,int t = 0,int next = 0):f(f),t(t),next(next){}	
}edge[maxm];
int tcnt,cnt;
void addedge(int f,int t){
	edge[cnt] = Edge(f,t,head[f]);
	head[f] = cnt++;
}

void spfa(int s){
    queue<int>q;
    for(int i = 1;i <= n;i++)dis[i] = INF;
    q.push(s);
    vis[s] = 1;
    dis[s] = 0;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i = head[u];~i;i = edge[i].next){
            int v = edge[i].to;
            if(dis[v] > dis[u] + edge[i].w){
                dis[v] = dis[u] + edge[i].w;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}

void dijkstra(int s){
	typedef pair <int,int> node;
	priority_queue<node,vector<node>,greater<node> >q;
	for(int i =1;i<=n;i++)dis[i] = INF;
	dis[s] = 0;
	q.push(make_pair(dis[s],s));
	while(!q.empty()){
		int u = q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u] = 1;
		for(int i = head[u];~i;i = edge[i].next){
			int v = edge[i].t;
			if(dis[v] > dis[u] + edge[i].w){
				dis[v] = dis[u] + edge[i].w;
				if(!vis[v]){
					q.push(make_pair(dis[v],v));
				}
			}
		}
	}
	return;
}

const int maxn = 10005;
const int maxm = 4e5+10;
const int INF = 1e9;
int head[maxn],parent[maxn],approve[maxn];
struct Edge{
	int from,to,next,w,cap,flow;
}edge[maxm];
int n,m,start,to,cnt,ans;//cnt = 0 so we can calculate "backedge" easily
void addedge(int from,int to,int cap,int flow){
	edge[cnt].cap = cap;
	edge[cnt].flow = flow;
	edge[cnt].to = to;
	edge[cnt].from = from;
	edge[cnt].next = head[from];
	head[from] = cnt++;
}
int BFS(int s,int t){
	queue<int>q;
	memset(approve,0,sizeof(approve)); 
	q.push(s);
	approve[s] = INF;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(int i = head[u];~i;i = edge[i].next){
			int v = edge[i].to;
			if(!approve[v] and edge[i].cap > edge[i].flow){
				parent[v] = i;
				approve[v] = min(approve[u],edge[i].cap - edge[i].flow);
				q.push(v);
			}
		}
		if(approve[t])break;
	}
	return approve[t];
}
int EK(int s,int t){
	int flow = 0;
	while(1){
		int delta = BFS(s,t);
		if(!delta)break;
		for(int u = t;u != s;u = edge[parent[u]].from){
			int curp = parent[u];
			edge[curp].flow += delta;
			edge[curp^1].flow -= delta;
		}
		flow += delta;
	}
	return flow;
}

addedge(f,t,w,0);
addedge(t,f,0,0);

struct Edge{
	int t,cap,flow,rev;
	bool is_rev;
};
vector<Edge>G[maxn];
int cur[maxn],dis[maxn],vis[maxn];
struct Dinic{
	int n;
	int flow = 0;
	void addedge(int f,int t,int cap,int flow,bool is_rev = 0){
		int rev_cnt = G[t].size();
		if(is_rev)rev_cnt--;
		G[f].push_back({t,cap,flow,rev_cnt,is_rev});
	}
	void add(int f,int t,int w){
		addedge(f,t,w,0,false);
		addedge(t,f,0,0,true);
	}
	void clear(){
		for(int i = 0;i <= n;i++){
			G[i].clear();
			G[i].shrink_to_fit();
			cur[i] = vis[i] = dis[i] = 0;
		}
		flow = 0;
		n = 0;
	}
	void init(int N){
        clear();
		n = N + 1;
	}
	bool BFS(int s,int t){
		for(int i = 0;i <= n;i++)cur[i] = 0;
		for(int i = 0;i <= n;i++)vis[i] = 0;
		queue<int>q;
		q.push(s);
		vis[s] = 1;
		dis[s] = 0;
		while(q.size()){
			int u = q.front();
			q.pop();
			for(auto it:G[u]){
				int v = it.t;
				if(!vis[v] and it.cap > it.flow){
					vis[v] = 1;
					dis[v] = dis[u] + 1;
					q.push(v);
				}
			}
		}
		return vis[t];
	}
	int DFS(int u,int T,int appr){
		if(u == T or !appr)return appr;
		int flow = 0,delta = 0;
		for(int & i = cur[u];i < (int)G[u].size();i++){
			auto it = G[u][i];
			int v = it.t;
			// cur[u] = i;
			if(dis[u] + 1 == dis[v] and (delta = DFS(v,T,min(appr,it.cap - it.flow))) > 0){
				G[u][i].flow += delta;
				G[v][it.rev].flow -= delta;
				flow += delta;
				appr -= delta;
				if(!appr)break;
			}
		}
		return flow;
	}
	
	int Maxflow(int s,int t){
		while(BFS(s,t)){
			// cout << "flow: " << flow << endl;
	 		flow += DFS(s,t,INF);
		}
		return flow;
	}
}dic;

const int maxn = 10005;
const int maxm = 4e5+10;
const int INF = 1e9;
int head[maxn],approve[maxn],dis[maxn],vis[maxn];
pair<int,int> parent[maxn];
struct Edge{
	int t,w,cap,flow,cost,rev;
	bool is_rev;
};
int n,m,start,to,cnt,ans,flow,cost;
vector<Edge>G[maxn];
void addedge(int f,int t,int cap,int flow,int cost,bool is_rev){
	int rev_cnt = G[t].size();
	if(is_rev)rev_cnt--;
	G[f].push_back({t,0,cap,flow,cost,rev_cnt,is_rev});
}
void add(int f,int t,int cap,int flow,int cost){
	addedge(f,t,cap,flow,cost,false);
	addedge(t,f,0,0,-cost,true);
}
int spfa(int s,int t){
	for(int i = 1;i <= n;i++){
		dis[i] = INF;
		vis[i] = 0;
		approve[i] = 0;
	}
	queue<int>q;
	q.push(s);
	approve[s] = INF;
	dis[s] = 0;
	vis[s] = 1;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for(int i = 0;i < G[u].size();i++){
			Edge it = G[u][i];
			int v = it.t;
			if(dis[v] > dis[u] + it.cost and it.cap > it.flow){
				parent[v] = {u,i};
				approve[v] = min(approve[u],it.cap - it.flow);
				dis[v] = dis[u] + it.cost;
				if(!vis[v]){
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
	return approve[t];
}
int EK(int s,int t){
//	int flow = 0;
	while(1){
		int delta = spfa(s,t);
		if(!delta)break;
		for(int u = t;u != s;u = parent[u].first){
			auto [curpx,curpy] = parent[u];
			G[curpx][curpy].flow += delta;
			int rev = G[curpx][curpy].rev;
			G[u][rev].flow -= delta;
		}
		flow += delta;
		cost += dis[t]*delta;
	}
	return flow;
}

int n,m;
cin >> n >> m;
int S = n+1,T = n+2;
N = T+1;
memset(head,-1,sizeof(head));
for(int i = 1;i <= m;i++){
	int f,t,l,u;
	cin >> f >> t >> l >> u;
	pflow[f] -= l,pflow[t] += l;
	lowedge[cnt] = l;
	add(f,t,u-l);
}
for(int i = 1;i <= n;i++){
	if(pflow[i] > 0)add(S,i,pflow[i]);
	else if(pflow[i] < 0)add(i,T,-pflow[i]);
}
Dinic(S,T);
bool ok = 1;
for(int i = head[S];~i;i = edge[i].next){
	if(edge[i].cap != edge[i].flow)ok = 0;
}
cout << (ok?"YES\n":"NO");
if(ok){
	for(int i = 0;i < m*2;i += 2)cout << edge[i].flow + lowedge[i] << endl;
}

int n,m,s1,t1;
	cin >> n >> m >> s1 >> t1;
	int S = n+1,T = n+2;
	N = T+1;
	memset(head,-1,sizeof(head));
	for(int i = 1;i <= m;i++){
		int f,t,l,u;
		cin >> f >> t >> l >> u;
		pflow[f] -= l,pflow[t] += l;
		lowedge[cnt] = l;
		add(f,t,u-l);
	}
	for(int i = 1;i <= n;i++){
		if(pflow[i] > 0)add(S,i,pflow[i]);
		else if(pflow[i] < 0)add(i,T,-pflow[i]);
	}
	add(t1,s1,INF);
	int flow = 0;
	Dinic(S,T);
	bool ok = 1;
	for(int i = head[S];~i;i = edge[i].next){
		if(edge[i].cap != edge[i].flow)ok = 0;
	}
	for(int i = head[s1];~i;i = edge[i].next){
		if(edge[i].t == t1){
			flow += abs(edge[i].flow);
			edge[i].flow = edge[i^1].flow = edge[i].cap = edge[i^1].cap = 0;
		}
	}
	flow += Dinic(s1,t1);
	if(ok){
		cout << flow;
	}
	else cout << "please go home to sleep";

int S = 2*n+1,T = 2*n+2;
	for(int i = 1;i <= n;i++){
		add(S,i,1);
		add(i+n,T,1);
	}
	for(int i = 1;i <= m;i++){
		int f,t;
		cin >> f >> t;
		add(f,t+n,1);
	}
	N = T;
	int ans = Dinic(S,T);

void solution(){
	static int nxt[maxn],has[maxn];
	for(int i = 1;i <= n;i++)nxt[i] = -1,has[i] = 0;
	for(int i = 0;i <= cnt;i+=2){
		int u = edge[i].f,v = edge[i].t - n;
		if(edge[i].flow == 1 and v > 1 and u <= n){
			nxt[u] = v;
			has[v] = 1;
		}
	}
	for(int i = 1;i <= n;i++)if(!has[i]){
		cout << i << " ";
		int u = nxt[i];
		while(u != -1){
			cout << u << " ";
			u = nxt[u];
		}
		cout << endl;
	}
}

bool KM(int u){
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].t;
		if(vis[v])continue;
		vis[v] = 1;
		if(!match[v] or KM(match[v])){
			match[v] = u;
			match[u] = v;
			return 1;
		}
	}
	return 0;
}
int match_cnt = 0;
for(int i = 1;i <= a;i++){
    for(int j = 0;j <= a+b;j++)vis[j] = 0;
    match_cnt += KM(i);
}
cout << match_cnt;

template <typename T>
struct hungarian {  // km
  int n;
  vector<int> matchx;  // 左集合对应的匹配点
  vector<int> matchy;  // 右集合对应的匹配点
  vector<int> pre;     // 连接右集合的左点
  vector<bool> visx;   // 拜访数组 左
  vector<bool> visy;   // 拜访数组 右
  vector<T> lx;
  vector<T> ly;
  vector<vector<T> > g;
  vector<T> slack;
  T inf;
  T res;
  queue<int> q;
  int org_n;
  int org_m;

  hungarian(int _n, int _m) {
    org_n = _n;
    org_m = _m;
    n = max(_n, _m);
    inf = numeric_limits<T>::max();
    res = 0;
    g = vector<vector<T> >(n, vector<T>(n));
    matchx = vector<int>(n, -1);
    matchy = vector<int>(n, -1);
    pre = vector<int>(n);
    visx = vector<bool>(n);
    visy = vector<bool>(n);
    lx = vector<T>(n, -inf);
    ly = vector<T>(n);
    slack = vector<T>(n);
  }

  void addEdge(int u, int v, int w) {
    g[u][v] = max(w, 0);  // 负值还不如不匹配 因此设为0不影响
  }

  bool check(int v) {
    visy[v] = true;
    if (matchy[v] != -1) {
      q.push(matchy[v]);
      visx[matchy[v]] = true;  // in S
      return false;
    }
    // 找到新的未匹配点 更新匹配点 pre 数组记录着"非匹配边"上与之相连的点
    while (v != -1) {
      matchy[v] = pre[v];
      swap(v, matchx[pre[v]]);
    }
    return true;
  }

  void bfs(int i) {
    while (!q.empty()) {
      q.pop();
    }
    q.push(i);
    visx[i] = true;
    while (true) {
      while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v = 0; v < n; v++) {
          if (!visy[v]) {
            T delta = lx[u] + ly[v] - g[u][v];
            if (slack[v] >= delta) {
              pre[v] = u;
              if (delta) {
                slack[v] = delta;
              } else if (check(v)) {  // delta=0 代表有机会加入相等子图 找增广路
                                      // 找到就return 重建交错树
                return;
              }
            }
          }
        }
      }
      // 没有增广路 修改顶标
      T a = inf;
      for (int j = 0; j < n; j++) {
        if (!visy[j]) {
          a = min(a, slack[j]);
        }
      }
      for (int j = 0; j < n; j++) {
        if (visx[j]) {  // S
          lx[j] -= a;
        }
        if (visy[j]) {  // T
          ly[j] += a;
        } else {  // T'
          slack[j] -= a;
        }
      }
      for (int j = 0; j < n; j++) {
        if (!visy[j] && slack[j] == 0 && check(j)) {
          return;
        }
      }
    }
  }

  void solve() {
    // 初始顶标
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        lx[i] = max(lx[i], g[i][j]);
      }
    }

    for (int i = 0; i < n; i++) {
      fill(slack.begin(), slack.end(), inf);
      fill(visx.begin(), visx.end(), false);
      fill(visy.begin(), visy.end(), false);
      bfs(i);
    }

    // custom
    for (int i = 0; i < n; i++) {
      if (g[i][matchx[i]] > 0) {
        res += g[i][matchx[i]];
      } else {
        matchx[i] = -1;
      }
    }
    cout << res << "\n";
    for (int i = 0; i < org_n; i++) {
      cout << matchx[i] + 1 << " ";
    }
    cout << "\n";
  }
};

int match[maxn],mvis[maxn];
void MVC(int u,int S,int T,bool flag){
	if(u == S or u == T)return;
	mvis[u] = 1;
	if(flag){
		if(!mvis[match[u]])MVC(match[u],S,T,!flag);
	}
	else{
		for(int i = head[u];~i;i = edge[i].next){
			int v = edge[i].to;
			if(mvis[v])continue;
			MVC(v,S,T,!flag);
		}
	}
}