//----------tarjan求2-sat--------------------------------------
#include <iostream>
using namespace std;
const int maxn=5000,maxm=3000000;
inline int Min(int a,int b){return a<b?a:b;}
struct Edge
{
int y,ne;
};
struct Tarjan_Strong_Connected
{
int d[maxn],low[maxn],index;
int *st,ee;
Edge *e;
int n;
int s[maxn],ss;
bool cs[maxn];
int color[maxn],cc;//环染色,0 .. cc-1,cc表示环数
void init(Edge* _e,int* _st,int _ee,int _n)
{
e=_e;st=_st;ee=_ee;n=_n;
for (int i=0;i<n;i++) d[i]=low[i]=cs[i]=0;
index=0;ss=-1;
cc=0;
}
void dfs(int u)
{
d[u]=low[u]=++index;
s[++ss]=u;
cs[u]=1;
for (int i=st[u];i!=-1;i=e[i].ne)
if (d[e[i].y]==0)
{
dfs(e[i].y);
low[u]=Min(low[u],low[e[i].y]);
}
else if (cs[e[i].y])
low[u]=Min(low[u],d[e[i].y]);
if (d[u]==low[u])
{
while (s[ss]!=u)
{
color[s[ss]]=cc;
cs[s[ss--]]=0;
}
color[s[ss]]=cc;
cs[s[ss--]]=0;
cc++;
}
}
void work()
{
for (int i=0;i<n;i++) if (d[i]==0) dfs(i);
}
};
struct Two_Sat //点0..2n-1,一个点i的对立点为i^1
{
Edge e[maxm];
int st[maxn],ee;
int n; //顶点数,即对数*2
Tarjan_Strong_Connected T;
void addedge(int x,int y) //手动添加边,加入约束条件的变,选了x,就一定要选y,有向边,边的方向一致即可
{
e[ee].y=y;e[ee].ne=st[x];st[x]=ee++;
}
void init(int _n) //初始化 传进点对数*2 编号从0开始
{
ee=0;
n=_n;
int i;
for (i=0;i<n;i++) st[i]=-1;
}
int work()
{
T.init(e,st,ee,n);
T.work(); //Tarjan 将环染色0 .. T.cc-1
int i,j;
for (i=0;i<n;i++) if (T.color[i]==T.color[i^1]) return 0; //判无解
return 1;
}
};
Two_Sat T;
inline void get(int& a)
{
char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
for (a=0;ch>='0'&&ch<='9';ch=getchar()) a=a*10+ch-48;
}
int main()
{
#ifdef _DEBUG
freopen("in.in","r",stdin);
#endif
int i,j,k;
int n,m;
while (scanf("%d%d",&n,&m)!=EOF)
{
T.init(n*2);
char ch1,ch2;
while (m--)
{
scanf(" %c",&ch1);
get(i);
scanf(" %c",&ch2);
get(j);
i=i*2-2;j=j*2-2;
if (ch1=='+'&&ch2=='+')
{
T.addedge(i+1,j);
T.addedge(j+1,i);
}
else
if (ch1=='-'&&ch2=='-')
{
T.addedge(i,j+1);
T.addedge(j,i+1);
}
else
if (ch1=='+'&&ch2=='-')
{
T.addedge(i+1,j+1);
T.addedge(j,i);
}
else
{
T.addedge(i,j);
T.addedge(j+1,i+1);
}
}
printf("%d\n",T.work());
}
return 0;
}
//----------两遍dfs求2-sat,可输出方案数--------------------------------
#include <iostream>
#include <vector>
using namespace std;
#define REP(i,h) for (i=0;i<(h);i++)
#define MAXNODE 2100
vector<int> g1[MAXNODE], g2[MAXNODE];
///// int g[MAXNODE][MAXNODE];
int fn[MAXNODE], color[MAXNODE];
int n, tot;
void dfs( int x ) {
if ( !color[x] ) {
int i; color[x] = 1;
//REP(i,n) if ( g[x][i] ) dfs( i );
for ( i = 0; i < g1[x].size(); i++ )
dfs( g1[x][i] );
fn[--tot] = x;
}
}
void ndfs( int x, int c ) {
if ( !color[x] ) {
int i; color[x] = c;
// REP(i,n) if ( g[i][x] ) ndfs( i, c );
for ( i = 0; i < g2[x].size(); i++ )
ndfs( g2[x][i], c );
}
}
inline void addedge( int i, int j ) { //选了j^1,就必须选i;选了i^1,就必须选j;
//g[i][j^1] = g[j][i^1] = 1;
g1[i].push_back( j^1 ); g2[j^1].push_back( i );
g1[j].push_back( i^1 ); g2[i^1].push_back( j );
}
bool twoSAT() {
tot = n; int i;
REP(i,n) color[i] = 0;
REP(i,n) dfs(i);
REP(i,n) color[i] = 0;
REP(i,n) ndfs(fn[i],i+1);
REP(i,n) if (color[i]==color[i^1]) return false;
return true;
}
bool initData() {
int m;
while ( scanf( "%d%d", &n, &m ) == EOF ) return false;
while ( m-- ) {
char c1; int tmp1;
while ( scanf( "%c", &c1 ), c1!='+' && c1!='-' );
scanf( "%d", &tmp1 );
tmp1--;
tmp1 = tmp1<<1;
if ( c1 == '+' ) tmp1++;
char c2; int tmp2;
while ( scanf( "%c", &c2 ), c2!='+' && c2!='-' );
scanf( "%d", &tmp2 );
tmp2--;
tmp2 = tmp2<<1;
if ( c2 == '+' ) tmp2++;
addedge( tmp1, tmp2 );//将矛盾方,不能在同一边的点,加入
}
return true;
}
void print_Method()
{
int i;
for (i=0;i<n;i++)
if ( color[i]<color[i^1] && i > 1 )//利用限制判断矛盾
printf("%d", i/2);
}
int main() {
while ( initData() ) {
int i;
n<<=1; // 把点分裂成两个点
//if ( twoSAT() ) solof2SAT(); else error();
printf( "%d\n", twoSAT() ? 1 : 0 );
print_Method();
REP(i,n) g1[i].clear(), g2[i].clear();
}
return 0;
}