# include <iostream>
using namespace std;
struct set
{
	int data;
	set *next;
	set *prev;
};
set *first=NULL;
set *last=NULL;
bool isempty()
{
	if (first==NULL)
		return 1;
	else
		return 0;
}
void del_last(){
	set *tmp;
	tmp=last;
	last=tmp->prev;
	last->next=NULL;	
}
void del_first()
{
	set *tmp;
	tmp=first;
	first=NULL;
	first=tmp->next;
	first->prev=NULL;
}
void add(set info)
{	
	set *tmp;
	tmp = new set;
	*tmp=info;
	if(first==NULL){
		first=tmp;
		first->next=NULL;
		first->prev=NULL;
		last=first;
	}
	else{
		last->next=tmp;
		last->next->prev=last;
		last=last->next;
		last->next=NULL;
	}
}
void deleteafter(int n)
{
	set *tmp;
	if(isempty()==0){
		set *flag;
		flag=first;
		while(flag->data!=n){
			flag=flag->next;
		}
		if(flag->next==last)
			del_last();
		else{
			flag->next=flag->next->next;
			flag->next->prev=flag;
		}
	}
}
void purgelist()
{
	set *flag;
	flag=first;
	if(isempty()==0){
		while(flag){
			set *tmp;
			tmp=flag;
			int d;
			d=flag->data;
			while(tmp){
				tmp=tmp->next;
				if(d==tmp->data){
					tmp=tmp->prev;
					deleteafter(tmp->data);
				}
			}
			flag=flag->next;
		}
	}	
}
int main()
{
	set arr[10];
	arr[1].data=1;
	arr[0].data=1;
	add(arr[0]);add(arr[1]);
	for(int i=2;i<10;i++){
		arr[i].data=i+1;
		add(arr[i]);
	}
	
	set *flag;
	flag=first;
	purgelist();
	while(flag){
		cout << flag->data << " _ ";
		flag=flag->next;
	}
	cout << endl;
	flag=last;
	while(flag){
		cout << flag->data << " _ ";
		flag = flag->prev;
	}
	return 0;
}