#include <stdio.h>
#include <stdlib.h>

#ifndef DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#endif

typedef struct Node {
    int val;
    struct Node *next;
} node;

int enqueue(node **head, node **tail, int val) {
    node *new;
    new = (node *) malloc (sizeof(node));
    if(!new) return -1;

    new->val = val;
    new->next = NULL;

    if(!*head) {
        *head = new;
        *tail = new;
    } else {
        (*tail)->next = new;
        *tail = (*tail)->next;
    }
    return 0;
}

int dequeue(node **head, node **tail) {
    node *t;

    if(!*head) return -1;
    else if(*head==*tail) *tail = NULL;

    DEBUG("Dequeue: %d\n",(*head)->val);

    t = (*head)->next;
    free(*head);
    *head = t;
    return 0;
}

int print(node *head) {
    node *trenutni;

    if(!head) return -1;

    for(trenutni=head; trenutni!=NULL; trenutni=trenutni->next)
        printf("%d ", trenutni->val);
    return 0;
}


void proguraj_lista(node **head, node **tail, int broj) {

    if (*head==NULL) return;
    else if (*head==*tail) return;
    else if(broj==1) return;
    node *temp, *temp1, *temp2;
    if(broj==2){
        temp=(*head)->next;
        (*head)->next=(*head)->next->next;
        temp->next=*head;
        *head = temp;
    }
    else{
    for(temp = *head; broj>3 && temp != NULL; temp = temp->next) broj--;
    if(temp == NULL) return;
    if(temp->next == NULL) return;
    if(temp->next->next == NULL) return;
    temp1 = temp->next;
    temp2 = temp->next->next;
    temp1->next = temp2->next;
    temp2->next = temp1;
    temp->next = temp2;
    if(temp->next->next->next == NULL) *tail = temp->next->next;

    /*
    for(temp=*head, i=3; i<broj; temp=temp->next, i++);
        temp1=temp->next;
        temp2=temp->next->next;

        temp->next=temp2;
        temp1->next=temp2->next;
        temp2->next=temp1;
    }*/
    }
}

int main() {
    node *head = NULL;
    node *tail = NULL;
    int menu_choice, val, ret_val, broj;
    char c;

    setbuf(stdout, NULL);
    do {
        menu_choice = 0;
        DEBUG("\n1 guranje elementa za jedno mjesto unaprijed (proguraj_lista)");
        DEBUG("\n2 dodaj(enqueue)\n3 brisi (dequeue)\n4 ispis (print)\n5 izlaz\n");
        scanf("%d", &menu_choice);
        switch (menu_choice) {
            case 1:
                scanf("%d",&broj);
                proguraj_lista(&head, &tail, broj);
                break;
            case 2:
                scanf("%d", &val);
                ret_val = enqueue(&head, &tail, val);
                if(ret_val==-1) DEBUG("Alokacija nije uspjela.");
                break;
            case 3:
                ret_val = dequeue(&head, &tail);
                if(ret_val==-1) DEBUG("Red je prazan.");
                break;
            case 4:
                ret_val = print(head);
                if(ret_val==-1) DEBUG("Red je prazan.");
                break;
            case 5:
                break;
            default:
                while((c = getchar()) != '\n' && c != EOF);
        }
    } while(menu_choice!=5);
    return 0;
}


///... temp   temp1         ...
///         temp->next    temp1->next
/// 1 2 3 4 5